Submission #655303

#TimeUsernameProblemLanguageResultExecution timeMemory
655303600MihneaInside information (BOI21_servers)C++17
0 / 100
13 ms17304 KiB
#include <bits/stdc++.h> using namespace std; const int N=240000+7; int n; int k; vector<pair<int, int>> gg[N]; vector<pair<int,int>> q2[N]; vector<int> q1[N]; const int K = 20; int p[N]; int dep[N]; int euler_tour[2 * N]; int tour_sz; int first_time_on_tour[N]; int last_time_on_tour[N]; int lg2[2 * N]; int idup[N]; //vector<int> g[N]; pair<int, int> tab_lca[2 * N][K]; void dfs_lca(int a, int par = -1) { p[a] = par; euler_tour[++tour_sz] = a; first_time_on_tour[a] = last_time_on_tour[a] = tour_sz; for (auto &it : gg[a]) { int b=it.first; int i=it.second; if (b==par){ continue; } idup[b]=i; dep[b] = 1 + dep[a]; dfs_lca(b, a); euler_tour[++tour_sz] = a; last_time_on_tour[a] = tour_sz; } } void lcaTM() { dfs_lca(1); for (int i = 2; i <= tour_sz; i++) { lg2[i] = 1 + lg2[i / 2]; } for (int i = 1; i <= tour_sz; i++) { tab_lca[i][0] = {dep[euler_tour[i]], euler_tour[i]}; } for (int k = 1; (1 << k) <= tour_sz; k++) { for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++) { tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]); } } } int lca(int a, int b) { if (first_time_on_tour[a] > last_time_on_tour[b]) { swap(a, b); } a = first_time_on_tour[a]; b = last_time_on_tour[b]; int k = lg2[b - a + 1]; return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second; } int sol[N]; int tp[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen("___input___.txt","r",stdin); cin>>n>>k; for(int i=1;i<=n+k-1;i++){ string s; cin>>s; assert(s=="S"||s=="Q"||s=="C"); if(s=="S"){ int a,b; cin>>a>>b; ///g[a].push_back(b); ///g[b].push_back(a); gg[a].push_back({b, i}); gg[b].push_back({a, i}); sol[i]=-1; } if(s=="Q"){ int a,b; cin>>a>>b; q2[a].push_back({b, i}); tp[i]=1; sol[i]=-2; } if(s=="C"){ int a; cin>>a; q1[a].push_back(i); sol[i]=-3; } } /// solve q1 for the general case lcaTM(); for (int a=1;a<=n;a++){ for (auto &it:q2[a]){ int b=it.first,i=it.second; /** **/ /// drumul de la b la a e crescator? vector<int> guys_x,guys_y; int x=a,y=b,z; swap(x,y); z=lca(x,y); while (x!=z){ guys_x.push_back(idup[x]); x=p[x]; } while(y!=z){ guys_y.push_back(idup[y]); y=p[y]; } vector<int> guys=guys_x; reverse(guys_y.begin(),guys_y.end()); for (auto &V:guys_y){ guys.push_back(V); } bool ok=1; guys.push_back(i); /* cout<< " ---> "; for (auto &it : guys){ cout<<it<<" "; } cout<<"\n";*/ for (int it=1;it<(int)guys.size();it++){ ok&=(guys[it-1]<guys[it]); } sol[i]=ok; } } for (int i=1;i<=n+k-1;i++){ if(tp[i]==1){ assert(sol[i]==0||sol[i]==1); if(sol[i]==1){ cout<<"yes\n"; }else{ cout<<"no\n"; } } } return 0; }

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("___input___.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...