/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 4.57 MiB
#2 Accepted 4ms 4.578 MiB
#3 Accepted 46ms 4.598 MiB
#4 Accepted 47ms 4.812 MiB
#5 Accepted 53ms 4.77 MiB
#6 Accepted 62ms 5.086 MiB
#7 Accepted 61ms 5.035 MiB
#8 Accepted 76ms 5.855 MiB
#9 Accepted 80ms 5.957 MiB
#10 Accepted 77ms 6.539 MiB
#11 Accepted 486ms 8.645 MiB
#12 Time Exceeded ≥2098ms ≥17.637 MiB
#13 Time Exceeded ≥2097ms ≥17.43 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll, ll>                   PII;
const int mx = 1e5 + 5;
int K , Ans[mx], arr[mx],freq[mx] , F[mx] ;
int cnt=0;
vector<int>edge[mx];
int out[mx],in[mx];
vector<int>convert_A; 
struct Query
{
    int index, l, r ;
    bool operator < (const Query &other)const
    {
        int block_own = l/ K ;
        int block_other = other.l / K ;
        return(block_other == block_own) ? r < other.r : block_own < block_other ;
    }

} query[mx];
void add(int index)
{
    freq[arr[convert_A[index]-1]]++ ;
}
void remove (int index)
{
   freq[arr[convert_A[index]-1]]-- ;
}
void dfs(int x,int p){
    in[x]=out[x]=cnt++;
    convert_A.push_back(x);
    for(auto u:edge[x]){
    	if(u!=p){
    		dfs(u,x);
    	}
    }
    out[x]=cnt;
}
void solve()
{
    int n , q ; cin >> n ;
    for(int i = 0 ; i <= n ; i++) freq[i] = 0 ;
    for(int i = 0 ; i < n ; i++) cin >> arr[i] ;
    for(int i=1;i<n;i++){
    	int x,y;
    	cin>>x>>y;
    	edge[x].push_back(y);
    	edge[y].push_back(x);
    }
    cnt=0;
    dfs(1,-1);
    K = sqrt(n) ;
    cin >> q ;
    for(int i = 0 ; i < q ; i++){
    	int x;
    	 cin >> x;
    	 query[i].l=in[x], query[i].r=out[x]-1 , query[i].index = i;
    	 }
    sort(query , query + q) ;
    int l = 0, r = -1 ;
    for(int i = 0 ; i < q ; i++)
    {
        while(r < query[i].r) add(++r ) ;
        while(l < query[i].l) remove(l++) ;
        while(r > query[i].r) remove(r-- );
        while(l > query[i].l) add(--l) ;
        int cnt = 0 ;
        int dis = query[i].r - query[i].l + 1 ;
        for(int j = 1 ; j <= dis ; j++){
            if(!freq[j]) cnt++ ;
        }
        Ans[query[i].index] = cnt;
    }
    convert_A.clear();
    for(int i=1;i<=n;i++)edge[i].clear();
    for(int i = 0 ; i < q ; i++) cout<< Ans[i] << "\n" ;
}
int main()
{
     __Heart__
    // READ("input7.txt") ;
   // WRITE("output7.txt") ;
     int t ; cin >> t ; while(t--) solve() ;
}

Information

Submit By
Type
Submission
Problem
P1157 Roy and Tree Permutation
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-01 10:03:25
Judged At
2025-01-01 10:03:25
Judged By
Score
25
Total Time
≥2098ms
Peak Memory
≥17.637 MiB