Submission #166809

#TimeUsernameProblemLanguageResultExecution timeMemory
166809YaroslaffBirthday gift (IZhO18_treearray)C++14
100 / 100
2382 ms98416 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define double long double #define f first #define s second #define mp make_pair #define pb push_back #define RE(i,n) for (int i = 1; i <= n; i++) #define RED(i,n) for (int i = n; i > 0; i--) #define REPS(i,n) for(int i = 1; (i*i) <= n; i++) #define REP(i,n) for (int i = 0; i < (int)n; i++) #define FOR(i,a,b) for (int i = a; i < b; i++) #define REPD(i,n) for (int i = n-1; i >= 0; i--) #define FORD(i,a,b) for (int i = a; i >= b; i--) #define all(v) v.begin(),v.end() #define pii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl; #define debug(x) cout << x << endl; #define debug2(x,y) cout << x << " " << y << endl; #define debug3(x,y,z) cout << x << " " << y << " " << z << endl; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int INF = 1e18+1; const int MOD = 1e9+7; const double PI = 3.14159265358979323846264338; int raise(int a,int n,int m = MOD){ if(n == 0)return 1; if(n == 1)return a; int x = 1; x *= raise(a,n/2,m); x %= m; x *= x; x %= m; if(n%2)x*= a; x %= m; return x; } int floor1(int n,int k){ if(n%k == 0 || n >= 0)return n/k; return (n/k)-1; } int ceil1(int n,int k){ return floor1(n+k-1,k); } const int LG = 18; const int N = 2e5+1; vector<int> adj[N]; int n,m,q; int pre[N][LG]; int a[N]; int dist[N]; set<int> ex[N]; set<int> ah[N]; void dfs(int u,int p){ pre[u][0] = p; RE(i,LG-1){ pre[u][i] = pre[pre[u][i-1]][i-1]; } for(int v:adj[u]){ if(v == p)continue; dist[v] = dist[u]+1; dfs(v,u); } } int lca(int u,int v){ if(dist[v] > dist[u])swap(u,v); for(int i = LG-1;i > -1;i--){ if(dist[pre[u][i]] >= dist[v]){ u = pre[u][i]; } } for(int i = LG-1;i > -1;i--){ if(pre[u][i] != pre[v][i]){ u = pre[u][i]; v = pre[v][i]; } } if(u == v)return u; return pre[u][0]; } void solve(){ cin >> n >> m >> q; RE(i,n-1){ int a,b;cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } dist[1] = 1; dfs(1,0); RE(i,m){ cin >> a[i]; ah[a[i]].insert(i); } RE(i,m-1){ ex[lca(a[i],a[i+1])].insert(i); } while(q--){ int ty;cin >> ty; if(ty == 1){ int ind,ok;cin >> ind >> ok; if(ind < m){ ex[lca(a[ind],a[ind+1])].erase(ind); } if(ind > 1){ ex[lca(a[ind-1],a[ind])].erase(ind-1); } ah[a[ind]].erase(ind); a[ind] = ok; if(ind < m){ ex[lca(a[ind],a[ind+1])].insert(ind); } if(ind > 1){ ex[lca(a[ind-1],a[ind])].insert(ind-1); } ah[a[ind]].insert(ind); } else{ int k; int l,r;cin >> l >> r >> k; if(ex[k].size() and *ex[k].begin() < r){ //cout << "NICENICE " << r << endl; //print(ex[k]); auto one = ex[k].upper_bound(r-1); one--; //cout << *one << endl; if(*one >= l and *one < r){ cout << *one << " " << *one+1 << endl; continue; } } if(ah[k].size() and *ah[k].begin() <= r){ auto one = ah[k].upper_bound(r);one--; if(*one >= l){ cout << *one << " " << *one << endl; continue; } } /* auto two = ah[k].upper_bound(r+1); one--;two--; if(one != ex[k].end() and *one >= l){ } else if(two != ah[k].end() and *two >= l){ cout << *two << " " << *two << endl; }*/ cout << "-1 -1\n"; } } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen(".in","r",stdin);freopen(".out","w",stdout); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...