제출 #346892

#제출 시각아이디문제언어결과실행 시간메모리
346892knightron0Birthday gift (IZhO18_treearray)C++14
0 / 100
49 ms91884 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define fr first #define sc second #define clr(a) memset(a, 0, sizeof(a)) #define sz(x) x.size() #define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl; #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, x, y) for (int i = x; i < y; i++) #define DEC(i, x, y) for (int i = x; i >= y; i--) #define all(v) v.begin(), v.end() #define min3(a, b, c) min(a, min(b, c)) #define max3(a, b, c) max(a, max(b, c)) #define alla(a, n) a, a + n #define gcd(a, b) __gcd(a, b) #define lcm(a, b) (a * b)/gcd(a, b) #define int long long int #define ull unsigned long long #define printarray(arr, n) for(int i= 0;i<n;i++) cout<<arr[i]<<' '; cout<<endl; #define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl; #define initdp(a) memset(a, -1, sizeof(a)); #define endl '\n' #define float long double using namespace std; const int MOD = 1e9 + 7; const int INF = 2e15; const int MAXN = 1e5 + 5; int fastexpo(int b, int exp){ if(exp == 0) return 1; if(exp == 1) return b; int ans = (fastexpo(b,exp/2) % MOD); ans *= ans; ans %= MOD; if(exp % 2 == 1){ ans *= b; } ans %= MOD; return ans; } set<int> prlca[MAXN]; set<int> sngle[MAXN]; vector<int> adj[MAXN]; int up[MAXN][100]; int timer = 0; int tout[MAXN], tin[MAXN]; int n; int l; int a[MAXN]; void dfs(int v, int p){ timer++; tin[v] = timer; up[v][0] = p; for(int i=1;i<=l;i++){ up[v][i] = up[up[v][i-1]][i-1]; } for(int u: adj[v]){ if(u != p){ dfs(u, v); } } timer++; tout[v] = timer; } bool isanc(int a, int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; } void preprocess(){ timer = 0; clr(tout); clr(tin); l = ceil(log2(n)); clr(up); } int lca(int u, int v){ if(isanc(u, v)){ return u; } if(isanc(v, u)){ return v; } for (int i = l; i >= 0; i--) { if (!isanc(up[u][i], v)) u = up[u][i]; } return up[u][0]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m, q; cin>>n>>m>>q; for(int i= 0;i<n-1;i++){ int t1, t2; cin>>t1>>t2; adj[t1].pb(t2); adj[t2].pb(t1); } for(int i= 1;i<=m;i++){ cin>>a[i]; } preprocess(); dfs(1, 1); int mem[m+1]; for(int i=1;i<m;i++){ int lc = lca(a[i],a[i+1]); mem[i] = lc; prlca[lc].insert(i); sngle[a[i]].insert(i); } sngle[a[m]].insert(m); while(q--){ int t1; cin>>t1; if(t1==2){ int x, y, req; cin>>x>>y>>req; auto it = prlca[req].lower_bound(x); int mn = -1; if(it != prlca[req].end()){ mn = *it; } auto it2 = sngle[req].lower_bound(x); int mn2 = -1; if(it2 != sngle[req].end()){ mn2 = *it2; } if((mn >= x && mn <= y) || (mn2 >= x && mn2 <= y)){ if(mn2 >= x && mn2 <= y && mn2+1 <= m && mn2 >= 1){ cout<<mn2<<' '<<mn2<<endl; continue; } else { if(mn >= x && mn+1 <= y && mn+1 <= m && mn >= 1){ cout<<mn<<' '<<mn+1<<endl; continue; } } } cout<<"-1 -1"<<endl; }else { int x, y; cin>>x>>y; sngle[a[x]].erase(sngle[a[x]].find(x)); sngle[y].insert(x); // x-1, x if(x > 1) { int prev = mem[x-1]; int newlca = lca(a[x-1], y); if(prev != newlca){ prlca[prev].erase(prlca[prev].erase(x-1)); prlca[newlca].insert(x-1); } } // x, x+1 if(x < m){ int prev = mem[x]; int newlca = lca(a[x+1], y); if(prev != newlca){ prlca[prev].erase(prlca[prev].erase(x)); prlca[newlca].insert(x); } } a[x]= y; } } 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...