oj.uz

Submission #748950

# Submission time Handle Problem Language Result Execution time Memory
748950 2023-05-27T07:59:10 Z WongChun1234 Tourism (JOI23_tourism) C++14
34 / 100
 5000 ms 32716 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=100050;
int n,m,q,u,v,c[N],sz[N],ch[N],pre[N],post[N],lift[20][N],pt;
int hd[N],rpar[N],bit[N],lcaa,ans[N];
vector<int> adj[N];
vector<pair<int,int>> qs[N];
set<pair<int,int>> s;
void calcsize(int nde,int par){
    sz[nde]=1;
    for (int i:adj[nde]) if (i!=par){
        calcsize(i,nde);
        sz[nde]+=sz[i];
        if (sz[i]>sz[ch[nde]]) ch[nde]=i;
    }
}
void prehld(int nde,int par){
    lift[0][nde]=rpar[nde]=par;
    for (int i=1;i<19;i++) lift[i][nde]=lift[i-1][lift[i-1][nde]];
    pre[nde]=++pt;
    if (sz[nde]>1){
        hd[ch[nde]]=hd[nde];
        prehld(ch[nde],nde);
    }
    for (int i:adj[nde]) if (i!=par&&i!=ch[nde]){
        hd[i]=i;
        prehld(i,nde);
    }
    post[nde]=pt;
}
bool isa(int a,int b){
    return pre[a]<=pre[b]&&post[a]>=post[b];
}
int lca(int a,int b){
    if (isa(a,b)) return a;
    if (isa(b,a)) return b;
    for (int i=18;~i;i--) if (!isa(lift[i][a],b)) a=lift[i][a];
    return rpar[a];
}
void modify(int q,int v){
    for (;q<N;q+=q&-q) bit[q]+=v;
}
int query(int q){
    int ret=0;
    for (;q;q-=q&-q) ret+=bit[q];
    return ret;
}
vector<pair<pair<int,int>,int>> del;
int curr[N];
void add(int l,int r,int v){
	//cout<<"add "<<l<<" "<<r<<" "<<v<<"\n";
	//for (auto i:s) cout<<(i).first<<" "<<(i).second<<" ins\n";
    set<pair<int,int>>::iterator it;
    del.clear();
    it=s.upper_bound({l,INT_MIN});
    if ((*it).second>0) it--;
    while ((*it).second&&(*it).first<=r){
    	//cout<<(*it).first<<" "<<(*it).second<<"!\n";
    	int st=(*it).first;
    	it++;
    	s.erase(prev(it));
    	del.push_back({{st,(*it).first},(*it).second});
        modify((*it).second,-((*it).first-st+1));
        it++;
        s.erase(prev(it));
    }
    for (auto i:del){
    	if (i.first.first<l) s.insert({i.first.first,-i.second}),s.insert({l-1,i.second}),modify(i.second,l-i.first.first);
    	if (i.first.second>r) s.insert({r+1,-i.second}),s.insert({i.first.second,i.second}),modify(i.second,i.first.second-r);
	}
    s.insert({l,-v});
    s.insert({r,v});
    modify(v,r-l+1);
    //cout<<"end\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>q;
    for (int i=1;i<n;i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    calcsize(1,1);
    hd[1]=1;
    prehld(1,1);
    for (int i=1;i<=m;i++) cin>>c[i];
    for (int i=1;i<=q;i++){
        cin>>u>>v;
        qs[v].push_back({u,i});
    }
    //for (int i=1;i<=n;i++) cout<<i<<" "<<hd[i]<<" "<<rpar[i]<<"\n";
    s.insert({0,0});
    s.insert({INT_MAX,0});
    for (int i=1;i<=m;i++){
        if (i>1){
            u=c[i-1];
            v=c[i];
            lcaa=lca(u,v);
            while (u!=lcaa) add(pre[u],pre[u],i-1),u=rpar[u];
            while (v!=lcaa) add(pre[v],pre[v],i-1),v=rpar[v];
            add(pre[lcaa],pre[lcaa],i-1);
        	/*
            //cout<<u<<"-"<<v<<"\n";
            while (hd[u]!=hd[lcaa]){
            	//cout<<u<<"!\n";
                add(pre[hd[u]],pre[u],i-1);
                u=rpar[hd[u]];
            }
            while (hd[v]!=hd[lcaa]){
            	//cout<<v<<"?\n";
                add(pre[hd[v]],pre[v],i-1);
                v=rpar[hd[v]];
            }
            add(min(pre[u],pre[v]),max(pre[u],pre[v]),i-1);*/
        }
        //cout<<i<<":\n";
        //for (auto j:s) cout<<j.first<<" "<<j.second<<"\n";
        for (auto j:qs[i]){
            ans[j.second]=(j.first==i?1:query(m)-query(j.first-1));
        }
    }
    for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5160 KB Output is correct
14 Correct 4 ms 5160 KB Output is correct
15 Correct 12 ms 5272 KB Output is correct
16 Correct 11 ms 5204 KB Output is correct
17 Correct 10 ms 5204 KB Output is correct
18 Correct 10 ms 5164 KB Output is correct
19 Correct 9 ms 5164 KB Output is correct
20 Correct 9 ms 5204 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 KB Output is correct
23 Correct 3 ms 5204 KB Output is correct
24 Correct 3 ms 5204 KB Output is correct
25 Correct 3 ms 5204 KB Output is correct
26 Correct 3 ms 5204 KB Output is correct
27 Correct 3 ms 5076 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 4 ms 5164 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5160 KB Output is correct
14 Correct 4 ms 5160 KB Output is correct
15 Correct 12 ms 5272 KB Output is correct
16 Correct 11 ms 5204 KB Output is correct
17 Correct 10 ms 5204 KB Output is correct
18 Correct 10 ms 5164 KB Output is correct
19 Correct 9 ms 5164 KB Output is correct
20 Correct 9 ms 5204 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 KB Output is correct
23 Correct 3 ms 5204 KB Output is correct
24 Correct 3 ms 5204 KB Output is correct
25 Correct 3 ms 5204 KB Output is correct
26 Correct 3 ms 5204 KB Output is correct
27 Correct 3 ms 5076 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 4 ms 5164 KB Output is correct
30 Correct 10 ms 5552 KB Output is correct
31 Correct 13 ms 5512 KB Output is correct
32 Correct 13 ms 5688 KB Output is correct
33 Correct 13 ms 5588 KB Output is correct
34 Correct 13 ms 5676 KB Output is correct
35 Correct 12 ms 5588 KB Output is correct
36 Correct 15 ms 5588 KB Output is correct
37 Correct 15 ms 5760 KB Output is correct
38 Correct 369 ms 5812 KB Output is correct
39 Correct 375 ms 5944 KB Output is correct
40 Correct 370 ms 5956 KB Output is correct
41 Correct 370 ms 5844 KB Output is correct
42 Correct 366 ms 5952 KB Output is correct
43 Correct 362 ms 5788 KB Output is correct
44 Correct 175 ms 5872 KB Output is correct
45 Correct 137 ms 5736 KB Output is correct
46 Correct 164 ms 5872 KB Output is correct
47 Correct 146 ms 5736 KB Output is correct
48 Correct 123 ms 5840 KB Output is correct
49 Correct 174 ms 5740 KB Output is correct
50 Correct 7 ms 5588 KB Output is correct
51 Correct 6 ms 5556 KB Output is correct
52 Correct 6 ms 5552 KB Output is correct
53 Correct 7 ms 5624 KB Output is correct
54 Correct 6 ms 5588 KB Output is correct
55 Correct 7 ms 5680 KB Output is correct
56 Correct 4 ms 5172 KB Output is correct
57 Correct 4 ms 5432 KB Output is correct
58 Correct 13 ms 5588 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5156 KB Output is correct
2 Correct 3 ms 5156 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Execution timed out 5099 ms 25864 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 524 ms 17656 KB Output is correct
3 Correct 914 ms 19560 KB Output is correct
4 Correct 772 ms 20664 KB Output is correct
5 Correct 1120 ms 27600 KB Output is correct
6 Correct 1133 ms 27740 KB Output is correct
7 Correct 1139 ms 28000 KB Output is correct
8 Correct 1100 ms 27720 KB Output is correct
9 Correct 1267 ms 28060 KB Output is correct
10 Correct 1119 ms 27972 KB Output is correct
11 Correct 1141 ms 27716 KB Output is correct
12 Correct 1199 ms 28024 KB Output is correct
13 Correct 1149 ms 28224 KB Output is correct
14 Correct 1151 ms 29372 KB Output is correct
15 Correct 1174 ms 32716 KB Output is correct
16 Correct 1157 ms 28488 KB Output is correct
17 Correct 1177 ms 28544 KB Output is correct
18 Correct 1165 ms 28452 KB Output is correct
19 Execution timed out 5041 ms 29152 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5156 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 1136 ms 22340 KB Output is correct
5 Correct 1158 ms 23036 KB Output is correct
6 Correct 1386 ms 29024 KB Output is correct
7 Correct 1562 ms 31776 KB Output is correct
8 Correct 1637 ms 31752 KB Output is correct
9 Correct 1499 ms 31928 KB Output is correct
10 Correct 1504 ms 31516 KB Output is correct
11 Correct 1537 ms 31932 KB Output is correct
12 Correct 1510 ms 31780 KB Output is correct
13 Correct 1480 ms 31784 KB Output is correct
14 Correct 71 ms 9800 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5160 KB Output is correct
14 Correct 4 ms 5160 KB Output is correct
15 Correct 12 ms 5272 KB Output is correct
16 Correct 11 ms 5204 KB Output is correct
17 Correct 10 ms 5204 KB Output is correct
18 Correct 10 ms 5164 KB Output is correct
19 Correct 9 ms 5164 KB Output is correct
20 Correct 9 ms 5204 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 KB Output is correct
23 Correct 3 ms 5204 KB Output is correct
24 Correct 3 ms 5204 KB Output is correct
25 Correct 3 ms 5204 KB Output is correct
26 Correct 3 ms 5204 KB Output is correct
27 Correct 3 ms 5076 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 4 ms 5164 KB Output is correct
30 Correct 10 ms 5552 KB Output is correct
31 Correct 13 ms 5512 KB Output is correct
32 Correct 13 ms 5688 KB Output is correct
33 Correct 13 ms 5588 KB Output is correct
34 Correct 13 ms 5676 KB Output is correct
35 Correct 12 ms 5588 KB Output is correct
36 Correct 15 ms 5588 KB Output is correct
37 Correct 15 ms 5760 KB Output is correct
38 Correct 369 ms 5812 KB Output is correct
39 Correct 375 ms 5944 KB Output is correct
40 Correct 370 ms 5956 KB Output is correct
41 Correct 370 ms 5844 KB Output is correct
42 Correct 366 ms 5952 KB Output is correct
43 Correct 362 ms 5788 KB Output is correct
44 Correct 175 ms 5872 KB Output is correct
45 Correct 137 ms 5736 KB Output is correct
46 Correct 164 ms 5872 KB Output is correct
47 Correct 146 ms 5736 KB Output is correct
48 Correct 123 ms 5840 KB Output is correct
49 Correct 174 ms 5740 KB Output is correct
50 Correct 7 ms 5588 KB Output is correct
51 Correct 6 ms 5556 KB Output is correct
52 Correct 6 ms 5552 KB Output is correct
53 Correct 7 ms 5624 KB Output is correct
54 Correct 6 ms 5588 KB Output is correct
55 Correct 7 ms 5680 KB Output is correct
56 Correct 4 ms 5172 KB Output is correct
57 Correct 4 ms 5432 KB Output is correct
58 Correct 13 ms 5588 KB Output is correct
59 Correct 3 ms 5156 KB Output is correct
60 Correct 3 ms 5156 KB Output is correct
61 Correct 4 ms 5204 KB Output is correct
62 Execution timed out 5099 ms 25864 KB Time limit exceeded
63 Halted 0 ms 0 KB -