Submission #898995

#TimeUsernameProblemLanguageResultExecution timeMemory
898995AlishInside information (BOI21_servers)C++14
0 / 100
35 ms12752 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; #define endl '\n' #define pb push_back #define all(x) x.begin(), x.end() #define F first #define S second #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define debug(x) cerr<<#x<<" "<<x<<endl; const int N =2e5+23, L=23; const int INF=1e9+23; int IS[N], DS[N], h[N]; int par[N][L], st[N], ft[N], tim; int up[N]; vector<pii> g[N]; int n, q; vector<pair<pii, int>> Q; void dfs(int v, int p=1){ st[v]=tim++; for (auto pp: g[v]){ int u=pp.F, w=pp.S; if(u==p) continue; IS[u]=DS[u]=v; up[u]=w; par[u][0]=v; if(up[u]<up[v]) IS[u]=IS[v]; else DS[u]=DS[v]; dfs(u, v); } ft[v]=tim; } int jmp(int v, int d){ for (int i=0; i<L; i++) if(d>>i&1) v=par[v][i]; return v; } int D(int v, int u){ int tu=u, tv=v; if(st[v]<=st[u] && ft[v]>=ft[u]) return up[u]; int f=0; for (int i=L-1; i>=0; i--){ if(!(st[par[u][i]]<=st[v] && ft[par[u][i]]>=ft[v])) u=par[u][i]; if(!(st[par[v][i]]<=st[u] && ft[par[v][i]]>=ft[u])) v=par[v][i]; } if(up[v]>up[u]) return INF; return up[tu]; } bool ok(int v, int u, int i){ if(!(st[IS[v]]<=st[u] && ft[IS[v]]>=ft[u]))return 0; if(!(st[DS[u]]<=st[v] && ft[DS[u]]>=ft[v]))return 0; if(D(v, u)<=i) return 1; return 0; } int main() { fast_io Q.pb({{-1, -1}, -1}); cin>>n>>q; for (int i=1; i<=n+q-1; i++){ char c; cin>>c; if(c=='C') return 0; if(c=='Q'){ int u, v; cin>>v>>u; Q.pb({{v, u}, 0}); } else{ int u, v; cin>>v>>u; g[v].pb({u, i}); g[u].pb({v, i}); Q.pb({{v, u}, 1}); } } IS[1]=DS[1]=1; dfs(1); for (int j=1; j<L; j++) for (int i=1; i<=n; i++) par[i][j]=par[par[i][j-1]][j-1]; for (int i=1; i<=n+q-1; i++){ int t=Q[i].S; if(t==1) continue; else{ int u=Q[i].F.S, v=Q[i].F.F; if(ok(u, v, i))cout<<"yes"<<endl; else cout<<"no"<<endl; } } }

Compilation message (stderr)

servers.cpp: In function 'int D(int, int)':
servers.cpp:51:15: warning: unused variable 'tv' [-Wunused-variable]
   51 |     int tu=u, tv=v;
      |               ^~
servers.cpp:53:9: warning: unused variable 'f' [-Wunused-variable]
   53 |     int f=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...