Submission #655589

#TimeUsernameProblemLanguageResultExecution timeMemory
655589600MihneaInside information (BOI21_servers)C++17
62.50 / 100
3567 ms100600 KiB
#include <bits/stdc++.h> using namespace std; const int N=240000+7; const int K = 20; int n; int k; vector<pair<int, int>> gg[N]; vector<pair<int,int>> q2[N]; int q1[N]; int p[N]; int pskip[K][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]; vector<int> who_have_id[N]; int who_has_id[N]; void dfs_lca(int a, int par = 0) { p[a] = par; euler_tour[++tour_sz] = a; first_time_on_tour[a] = last_time_on_tour[a] = tour_sz; vector<pair<int, int>> ngg; for (auto &it : gg[a]) { int b=it.first; int i=it.second; if (b==par){ continue; } ngg.push_back(it); who_has_id[i]=b; idup[b]=i; dep[b] = 1 + dep[a]; dfs_lca(b, a); euler_tour[++tour_sz] = a; last_time_on_tour[a] = tour_sz; } gg[a]=ngg; } 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 goup(int a,int cnt){ assert(cnt>=0); for(int i=0;i<K;i++){ if(cnt&(1<<i)){ a=pskip[i][a]; } } return a; } int sol[N]; int tp[N]; int inc[N]; int dcr[N]; int cnt[N]; void dfs2(int a){ inc[a]=max(inc[a],1); dcr[a]=max(dcr[a],1); for (auto &it:gg[a]){ int b=it.first; if(b==p[a]){ continue; } if(idup[a]<idup[b]){ inc[b]=1+inc[a]; }else{ dcr[b]=1+dcr[a]; } dfs2(b); } ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n"; } int main() { if(0){ freopen("them.txt","r",stdin); freopen("output2.txt","w",stdout); /*char s[1000]; while(cin.getline(s,1000)){ if(s[0]!='Q'){ cout<<s<<"\n"; } }*/ string s; while(cin>>s){ if(s=="yes"||s=="no"){ continue; } cout<<s<<"\n"; } exit(0); } if(1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); else { freopen("___input___.txt","r",stdin); /// freopen("them.txt","r",stdin); if(0)freopen("out.txt","w",stdout); } cin>>n>>k; int cnt3=0; for(int i=1;i<=n+k-1;i++){ string s; cin>>s; assert(s=="S"||s=="Q"||s=="C"); if(s=="S"){ tp[i]=2; 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; if(a==b){ tp[i]=1; sol[i]=1; }else{ q2[a].push_back({b, i}); tp[i]=1; sol[i]=-2; } } if(s=="C"){ cnt3++; int a; cin>>a; /// cout<<i<<" = "<<a<<"\n"; q1[i]=a; sol[i]=-3; tp[i]=3; } } lcaTM(); dfs2(1); /// solve q1 for the general case for (int i=1;i<=n;i++){ pskip[0][i]=p[i]; } for (int k=1;k<K;k++){ for (int i=1;i<=n;i++){ pskip[k][i]=pskip[k-1][pskip[k-1][i]]; } } 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); int last=-1; if(y!=z){ last=idup[y]; }else{ last=idup[goup(x,dep[x]-dep[z]-1)]; } bool ok=1; ok&=(inc[y]>=dep[y]-dep[z]); ok&=(dcr[x]>=dep[x]-dep[z]); if(x!=z&&y!=z){ ok&=(idup[goup(x,dep[x]-dep[z]-1)]<=idup[goup(y,dep[y]-dep[z]-1)]); } ok&=(last<i); sol[i]=ok; } } const int INF=(int)1e9+7; int cnt_2=0; int ciq=0; // assert(p[2]==21); // assert(p[25]==21); // cout<<"sir = "<<idup[46]<<" "<<idup[2]<<" "<<idup[21]<<"\n"; for (int i=1;i<=n+k-1&&cnt3!=0;i++){ if(tp[i]==2){ cnt_2++; /// add edge int vertex=who_has_id[i],last=+INF; // cout<<vertex<<" "<<p[vertex]<<"\n"; while(p[vertex]){ if(idup[vertex]>last){ break; } last=idup[vertex]; cnt[vertex]++; vertex=p[vertex]; } } if (q1[i]){ ciq++; assert(tp[i]==3); int vertex=q1[i]; int ret=1,last=-INF; int init=vertex; for (auto &it : gg[vertex]){ int v2=it.first; ret+=cnt[v2]; } while (p[vertex]){ if (idup[vertex]<last){ break; } ret+=(idup[vertex]<i); for (auto &it:gg[p[vertex]]){ int v2=it.first; if(idup[vertex]<idup[v2]){ ret+=cnt[v2]; } } last=idup[vertex]; vertex=p[vertex]; } sol[i]=ret; if(ciq==194){ // cout<<"ret = "<<ret<<", query = "<<init<<"\n"; // return 0; } } } if(cnt3) assert(cnt_2==n-1); for (int i=1;i<=n+k-1;i++){ if(tp[i]==1){ assert(sol[i]==0||sol[i]==1); ///continue; if(sol[i]==1){ cout<<"yes\n"; }else{ cout<<"no\n"; } } if (tp[i]==3){ cout<<sol[i]<<"\n"; } } return 0; }

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:259:29: warning: unused variable 'init' [-Wunused-variable]
  259 |                         int init=vertex;
      |                             ^~~~
servers.cpp:119:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                 freopen("them.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen("output2.txt","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:139:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |                 freopen("___input___.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:141:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |                 if(0)freopen("out.txt","w",stdout);
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...