Submission #577159

#TimeUsernameProblemLanguageResultExecution timeMemory
577159Valters07Inside information (BOI21_servers)C++14
53 / 100
196 ms32716 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O2,unroll-loops") #define fio ios_base::sync_with_stdio(0);cin.tie(0); #define ll long long #define en cin.close();return 0; #define pb push_back #define fi first//printf("%lli\n",cur); #define se second//scanf("%lli",&n); #define r0 return 0; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 120005; const int LOG = log2(N)+2; vector<pair<int,int> > g[N]; int par[N][LOG], tin[N], tout[N], tt; int down[N], up[N], dep[N]; int topar[N]; void dfs(int u, int p) { tin[u]=++tt; par[u][0]=p; for(int i = 1;i<LOG;i++) par[u][i]=par[par[u][i-1]][i-1]; for(auto v:g[u]) { if(v.fi!=p) { topar[v.fi]=v.se; down[v.fi]=(v.se>topar[u]||u==1?down[u]+1:1); up[v.fi]=(v.se<topar[u]||u==1?up[u]+1:1); dep[v.fi]=dep[u]+1; dfs(v.fi,u); } } tout[u]=tt; } bool is_anc(int u, int v) { return (tin[u]<=tin[v]&&tout[v]<=tout[u]); } int main() { fio //ifstream cin("in.in"); int n, q; cin >> n >> q; vector<pair<pair<int,int>,int> > qu; for(int i = 1;i<n+q;i++) { char c; cin >> c; if(c=='C') return 0; int u, v; cin >> u >> v; if(c=='Q') qu.pb({{u,v},i}); else g[u].pb({v,i}), g[v].pb({u,i}); } dfs(1,1); for(auto i:qu) { int u = i.fi.fi, v = i.fi.se, t = i.se; swap(u,v); if(u==v) cout << "yes"; else if(is_anc(u,v)) cout << ((dep[v]-dep[u])<=down[v]&&topar[v]<t?"yes":"no"); else if(is_anc(v,u)) { int u1 = u; for(int i = LOG-1;i>=0;i--) if(!is_anc(par[u1][i],v)) u1=par[u1][i]; cout << ((dep[u]-dep[v])<=up[u]&&topar[u1]<t?"yes":"no"); } else { int u1 = u, v1 = v; for(int i = LOG-1;i>=0;i--) { if(!is_anc(par[u1][i],v)) u1=par[u1][i]; if(!is_anc(par[v1][i],u)) v1=par[v1][i]; } int lca = par[u1][0]; cout << (dep[u]-dep[lca]<=up[u]&&dep[v]-dep[lca]<=down[v]&& topar[u1]<topar[v1]&&topar[v]<t?"yes":"no"); } cout << "\n"; } //cin.close(); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...