oj.uz

Submission #954455

# Submission time Handle Problem Language Result Execution time Memory
954455 2024-03-28T01:10:01 Z owoovo Tourism (JOI23_tourism) C++17
24 / 100
 650 ms 37456 KB 
#include<bits/stdc++.h>
#define ll long long
#define MP make_pair
#define F first 
#define S second 
using namespace std;
int f[100010],si[100010],hs[100010],top[100010],dep[100010],in[100010],cnt;
int n,m,q;
vector<int> e[100010];
int dfs1(int now,int last){
    dep[now]=dep[last]+1;
    f[now]=last;
    si[now]=1;
    for(auto x:e[now]){
        if(x==last)continue;
        int siz=dfs1(x,now);
        if(siz>si[hs[now]]){
            hs[now]=x;
        }
        si[now]+=siz;
    }
    return si[now];
}
void dfs2(int now,int tp){
    in[now]=++cnt;
    top[now]=tp;
    if(hs[now]!=0)dfs2(hs[now],tp);
    for(auto x:e[now]){
        if(x==f[now]||x==hs[now])continue;
        dfs2(x,x);
    }
    return;
}
struct Bit{
    int ori[100010]={};
    void modify(int p,int x){
        if(p==0)return ;
        while(p<=100000){
            ori[p]+=x;
            p+=p&(-p);
        }
        return ;
    }
    int query(int p){
        int ans=0;
        while(p){
            ans+=ori[p];
            p-=p&(-p);
        }
        return ans;
    }
}bit;
int ans[100010],ver[100010];
vector<pair<pair<int,int>,int>> qu;
map<int,int> s;
void segin(int l,int r,int x){
    if(l>r)swap(l,r);
	auto lit = s.upper_bound(l);
	lit = prev(lit);
	int fl = lit->first;
	int fv = lit->second;
	int pv = 0;
	while(lit->first<=r){
		pv = lit->second;
		bit.modify(lit->second,-(next(lit)->first-lit->first));	
		auto k = lit;
		++lit;
		s.erase(k);
	}
	bit.modify(x,r-l+1);
	bit.modify(fv,l-fl);
	if(lit->first!=r+1){
		s[r+1] = pv;
		bit.modify(pv,lit->first-r-1);
	}
	s[fl] = fv;
	s[l] = x;
}
void putin(int u,int v,int id){
    while(1){
        //cout<<u<<" "<<v<<" "<<id<<"\n";
        if(top[u]==top[v]){
            segin(in[v],in[u],id);
            break;
        }
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        segin(in[top[u]],in[u],id);
        u=f[top[u]];
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
	s[1]=0;
	s[n+1]=0;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        cin>>ver[i];
    }
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        if(l==r){
            ans[i]=1;
            continue;
        }
        qu.push_back({{l,r},i});
    }
    sort(qu.begin(),qu.end());
    reverse(qu.begin(),qu.end());
    int now=0;
    for(int i=m-1;i>=1;i--){
        //cout<<i<<"ok\n";
        //put in i,i+1
        putin(ver[i],ver[i+1],i+1);
        while(now!=q&&qu[now].F.F==i){
            auto [x,id]=qu[now];
            auto [l,r]=x;
            ans[id]=bit.query(r);
            now++;
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4568 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4576 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4572 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 2 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4440 KB Output is correct
29 Runtime error 4 ms 8792 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4568 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4576 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4572 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 2 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4440 KB Output is correct
29 Runtime error 4 ms 8792 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 70 ms 15312 KB Output is correct
5 Correct 63 ms 18384 KB Output is correct
6 Correct 76 ms 19460 KB Output is correct
7 Correct 91 ms 21968 KB Output is correct
8 Correct 91 ms 21976 KB Output is correct
9 Correct 93 ms 21968 KB Output is correct
10 Correct 101 ms 22200 KB Output is correct
11 Correct 95 ms 21824 KB Output is correct
12 Correct 113 ms 21956 KB Output is correct
13 Correct 91 ms 21956 KB Output is correct
14 Correct 91 ms 21960 KB Output is correct
15 Correct 37 ms 18700 KB Output is correct
16 Runtime error 54 ms 37456 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 201 ms 10108 KB Output is correct
3 Correct 307 ms 10864 KB Output is correct
4 Correct 235 ms 11128 KB Output is correct
5 Correct 410 ms 14328 KB Output is correct
6 Correct 392 ms 14420 KB Output is correct
7 Correct 385 ms 14284 KB Output is correct
8 Correct 383 ms 14420 KB Output is correct
9 Correct 405 ms 14392 KB Output is correct
10 Correct 379 ms 14424 KB Output is correct
11 Correct 387 ms 14416 KB Output is correct
12 Correct 386 ms 14676 KB Output is correct
13 Correct 384 ms 14612 KB Output is correct
14 Correct 396 ms 15568 KB Output is correct
15 Runtime error 48 ms 21752 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 511 ms 13160 KB Output is correct
5 Correct 524 ms 13212 KB Output is correct
6 Correct 604 ms 16040 KB Output is correct
7 Correct 636 ms 17352 KB Output is correct
8 Correct 633 ms 17768 KB Output is correct
9 Correct 650 ms 17608 KB Output is correct
10 Correct 644 ms 17224 KB Output is correct
11 Correct 627 ms 17300 KB Output is correct
12 Correct 645 ms 17256 KB Output is correct
13 Correct 643 ms 17432 KB Output is correct
14 Correct 50 ms 7388 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4568 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4576 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4572 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 2 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4440 KB Output is correct
29 Runtime error 4 ms 8792 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -