oj.uz

Submission #90710

# Submission time Handle Problem Language Result Execution time Memory
90710 2018-12-24T00:16:02 Z janchomath Birthday gift (IZhO18_treearray) C++14
0 / 100
 67 ms 66548 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;

ll in[200020],l,r,n,m,xx,yy,q,a[200020],type,pa;
ll out[200020];
ll timer=1;
ll P[200020][18];
ll lvl[200020];
ll indx[2000000];
vector<ll>v[200005],g;

void dfs(int p,int u) {
    P[u][0]=p;
    for (int i=1;i<=17;i++)
        P[u][i]=P[P[u][i-1]][i-1];
    timer++;
    in[u]=timer;
    indx[in[u]] = u;
    for (int i=0;i<v[u].size();i++)
        if (v[u][i] != p){
        	lvl[v[u][i]]=lvl[u]+1;
            dfs(u,v[u][i]);
        }
    out[u]=timer;
}

int lca(int a,int b) {
    if (in[a] <= in[b] && out[b] <= out[a]) return a;
    for (int i=17;i>=0;i--)
        if (P[a][i])
            if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]]))
                a=P[a][i];
    return P[a][0];
}

set<ll>st[200005],st1[200005],st2[200005];

int main(){
	
	cin >> n >> m >> q;
	
	for(int i=1; i<n; i++){
		cin >> xx >> yy;
		v[xx].pb(yy);
		v[yy].pb(xx);
	}
	
	dfs(1,1);
	
	for(int i=1; i<=m; i++){
		cin >> a[i];
	}
	
	for(int i=1; i<=m; i++){
		xx = i;
		yy = a[i];
			st[yy].insert(xx);
			if(xx != 1){
				ll pp = lca(a[xx],a[xx-1]);
				pp = lca(yy,a[xx-1]);
				st1[pp].insert(xx);
			}
			if(xx != m){
				ll pp = lca(a[xx],a[xx+1]);
				pp = lca(yy,a[xx+1]);
				st2[pp].insert(xx+1);
			}
			a[xx] = yy;
	}
	
	while(q--){
		cin >> type;
		if(type == 1){
			cin >> xx >> yy;
			st[a[xx]].erase(st[a[xx]].find(xx));
			st[yy].insert(xx);
			if(xx != 1){
				ll pp = lca(a[xx],a[xx-1]);
				st1[pp].erase(st1[pp].find(xx));
				pp = lca(yy,a[xx-1]);
				st1[pp].insert(xx);
			}
			if(xx != m){
				ll pp = lca(a[xx],a[xx+1]);
				st2[pp].erase(st2[pp].find(xx));
				pp = lca(yy,a[xx+1]);
				st2[pp].insert(xx+1);
			}
			a[xx] = yy;
		}
		else {
			cin >> l >> r >> pa;
			if(st[pa].lower_bound(l) != st[pa].end()){
				if(*(st[pa].lower_bound(l)) <= r){
					cout << *(st[pa].lower_bound(l)) << " " << *(st[pa].lower_bound(l)) << endl;
					continue;
				}
			}
			if(st1[pa].lower_bound(l+1) != st1[pa].end()){
				if(*(st1[pa].lower_bound(l+1)) <= r){
					cout << *(st1[pa].lower_bound(l+1)) - 1<< " " << *(st1[pa].lower_bound(l+1)) << endl;
					continue;
				}
			}
			
			if(st2[pa].lower_bound(l) != st2[pa].end()){
				if(*(st2[pa].lower_bound(l)) < r){
					cout << *(st2[pa].lower_bound(l))<< " " << *(st2[pa].lower_bound(l)) + 1<< endl;
					continue;
				}
			}
			
			cout <<"-1 -1\n";
		}
	}
	
	
	
	
	return 0;
}

Compilation message

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[u].size();i++)
                  ~^~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33272 KB n=5
2 Runtime error 67 ms 66548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33272 KB n=5
2 Runtime error 67 ms 66548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33272 KB n=5
2 Runtime error 67 ms 66548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33272 KB n=5
2 Runtime error 67 ms 66548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -