oj.uz

Submission #158093

# Submission time Handle Problem Language Result Execution time Memory
158093 2019-10-14T18:26:06 Z brcode Birthday gift (IZhO18_treearray) C++14
0 / 100
 4000 ms 23928 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int dp[MAXN][25];
int depth[MAXN];
int seq[MAXN];
int holdlca[MAXN];
vector<int> v1[MAXN];
set<int> v2[MAXN];
set<int> v3[MAXN];
void dfs(int curr,int par,int dep){
    dp[curr][0] = par;
    depth[curr] = dep;
    for(int x:v1[curr]){
        if(x!=par){

            dfs(x,curr,dep+1);
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dp[a][j]!=-1 && depth[dp[a][j]]>=depth[b]){
            a = dp[a][j];
        }

    }
    if(a==b){
        return a;
    }
    for(int i=20;i>=0;i--){
        if(dp[a][i]!=-1 && dp[a][i]!=dp[b][i]){
            a = dp[a][i];
            b = dp[b][i];
        }
    }
    return dp[a][0];
}
int main(){
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    for(int i=1;i<=m;i++){
        cin>>seq[i];
        v3[seq[i]].insert(i);
    }
    dfs(1,-1,1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(dp[i][j-1]==-1){
                dp[i][j] = -1;
            }else{
                dp[i][j] = dp[dp[i][j-1]][j-1];
            }
        }
    }
    //cout<<123<<endl;
    for(int j=1;j<m;j++){
        holdlca[j] = lca(seq[j],seq[j+1]);
        v2[holdlca[j]].insert(j);
        
    }
  
    while(q--){
        int t;
        cin>>t;
      
            if(t==1){
                int pos,v;
                cin>>pos>>v;
                v3[seq[pos]].erase(v3[seq[pos]].find(pos));
                seq[pos] = v;
                v3[seq[pos]].insert(pos);
                int temp = holdlca[pos];
                v2[temp].erase(v2[temp].find(pos));
                temp  = holdlca[pos-1];
                v2[temp].erase(v2[temp].find(pos-1));
                holdlca[pos] = lca(seq[pos],seq[pos+1]);
                v2[holdlca[pos]].insert(pos);
                holdlca[pos-1] = lca(seq[pos-1],seq[pos]);
                v2[holdlca[pos-1]].insert(pos-1);
                
            }else{
                int l,r,v;
                cin>>l>>r>>v;
                //cout<<123<<" "<<v<<" "<<v2[v].size()<<endl;
                
                auto hold2= v3[v].lower_bound(l);
                if(hold2!=v3[v].end()){
                    int x = *hold2;
                    if(x<=r){
                        cout<<x<<" "<<x<<endl;
                        continue;
                    }
                
                }
                
                if(v2[v].size()==0){
                    cout<<-1<<" "<<-1<<endl;
                    continue;
                }
                auto hold =v2[v].lower_bound(l);
                int x = *hold;
                if(x<r){
                    cout<<x<<" "<<x+1<<endl;
                }else{
                    cout<<-1<<" "<<-1<<endl;
                }
            }
        
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Execution timed out 4094 ms 23928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Execution timed out 4094 ms 23928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Execution timed out 4094 ms 23928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB n=5
2 Execution timed out 4094 ms 23928 KB Time limit exceeded
3 Halted 0 ms 0 KB -