Submission #697594

#TimeUsernameProblemLanguageResultExecution timeMemory
697594jamezzzInside information (BOI21_servers)C++17
0 / 100
50 ms22740 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds; //less_equal for identical elements #ifdef DEBUG #define dbg(...) printf(__VA_ARGS__); #define getchar_unlocked getchar #else #define dbg(...) #endif #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define psf push_front #define ppb pop_back #define ppf pop_front #define sz(x) (int)x.size() #define mnto(x,y) x=min(x,(__typeof__(x))y) #define mxto(x,y) x=max(x,(__typeof__(x))y) #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(),x.end() #define lb(x,v) (lower_bound(all(x),v)-x.begin()) #define ub(x,v) (upper_bound(all(x),v)-x.begin()) #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef tuple<int,int,int> iii; typedef tuple<int,int,int,int> iiii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; mt19937 rng(time(0)); #define mod 1000000007 inline int add(int a,int b){ int r=a+b; while(r>=mod)r-=mod; while(r<0)r+=mod; return r; } inline int mult(int a,int b){ return (int)(((ll)(a*b))%mod); } inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } #define maxn 120005 int n,k,p[20][maxn],pwt[maxn],asc[maxn],des[maxn],dep[maxn],ans[maxn]; vii AL[maxn]; vi cqry[maxn]; vii qqry[maxn]; void dfs(int u,int par){ for(auto[v,w]:AL[u]){ if(v==par)continue; p[0][v]=u; if(pwt[u]==-1)asc[v]=des[v]=1; else if(w<pwt[u])asc[v]=asc[u]+1,des[v]=des[u]; else asc[v]=asc[u],des[v]=des[u]+1; dep[v]=dep[u]+1; pwt[v]=w; dfs(v,u); } } int fpar(int x,int k){ for(int i=19;i>=0;--i){ if((1<<i)<=k)x=p[i][x],k-=(1<<i); } return x; } int lca(int a,int b){ if(dep[a]<dep[b])swap(a,b); for(int k=19;k>=0;--k){ if(p[k][a]!=-1&&dep[p[k][a]]>=dep[b])a=p[k][a]; } if(a==b)return a; for(int k=19;k>=0;--k){ if(p[k][a]!=p[k][b])a=p[k][a],b=p[k][b]; } return p[a][0]; } pbds* dfs2(int u,int p,pbds *pset){ /* pf("dfs2: %d %d {",u,p); for(int i:*pset)pf("%d ",i); pf("}\n"); */ pbds *cset=new pbds(); for(int t:cqry[u])ans[t]+=(*pset).order_of_key(t); pbds *torem=new pbds(); for(auto[v,w]:AL[u]){ if(v==p)continue; if(w<pwt[u]){ (*pset).insert(w); pbds *rset=dfs2(v,u,pset); for(int x:*rset)(*pset).insert(x); (*rset).insert(w); for(int t:cqry[u])ans[t]+=(*rset).order_of_key(t); if(sz((*rset))>sz((*torem)))swap(*torem,*rset); for(int i:*rset)(*torem).insert(i); } else{ pbds *s=new pbds(); (*s).insert(w); pbds *rset=dfs2(v,u,s); (*rset).insert(w); for(int x:*rset)(*pset).insert(x); for(int t:cqry[u])ans[t]+=(*rset).order_of_key(t); if(sz((*rset))>sz((*cset)))swap(*rset,*cset); for(int i:*rset)(*cset).insert(i); } } for(int i:*torem)(*pset).erase(i); /* pf("pset %d: {",u); for(int i:*pset)pf("%d ",i); pf("}\n"); pf("cset %d: {",u); for(int i:*cset)pf("%d ",i); pf("}\n"); */ return cset; } int main(){ sf("%d%d",&n,&k); for(int i=0;i<n+k-1;++i){ char c;sf(" %c",&c); if(c=='S'){ int a,b;sf("%d%d",&a,&b); AL[a].pb({b,i}); AL[b].pb({a,i}); ans[i]=-3; } else if(c=='Q'){ int a,b;sf("%d%d",&a,&b); qqry[b].pb({a,i}); } else{ int a;sf("%d",&a); cqry[a].pb(i); } } for(int i=1;i<=n;++i)sort(all(AL[i]),[](ii &a,ii &b){return a.se>b.se;}); p[0][1]=-1; asc[1]=des[1]=0; pwt[1]=-1; dfs(1,0); #ifdef DEBUG for(int i=1;i<=n;++i){ pf("%d: asc %d, dec %d\n",i,asc[i],des[i]); } #endif for(int k=0;k<19;++k){ for(int i=1;i<=n;++i){ if(p[k][i]!=-1)p[k+1][i]=p[k][p[k][i]]; else p[k+1][i]=-1; } } //x --asc--> u --w1--> lca //y --w3--> smt --dec--> v --w2--> lca //w1 < w2 //w3 < t for(int x=1;x<=n;++x){ for(auto[y,t]:qqry[x]){ if(x==y){ ans[t]=-1; continue; } int l=lca(x,y); if(l==y){ int jmp=dep[x]-dep[y]; if(asc[x]>=jmp&&pwt[fpar(x,jmp-1)]<t)ans[t]=-1; else ans[t]=-2; } else if(l==x){ int jmp=dep[y]-dep[x]; if(des[y]>=jmp&&pwt[y]<t)ans[t]=-1; else ans[t]=-2; } else{ int jmpx=dep[x]-dep[l],jmpy=dep[y]-dep[l]; if(asc[x]<jmpx||des[y]<jmpy)ans[t]=-2; else if(pwt[fpar(x,jmpx-1)]>=pwt[fpar(y,jmpy-1)])ans[t]=-2; else if(pwt[y]>t)ans[t]=-2; else ans[t]=-1; } } } pwt[1]=INF; pbds *s=new pbds(); dfs2(1,-1,s); for(int i=0;i<n+k-1;++i){ if(ans[i]==-1)pf("yes\n"); else if(ans[i]==-2)pf("no\n"); else if(ans[i]!=-3)pf("%d\n",ans[i]+1); } } /* 6 9 S 1 2 S 1 3 S 3 4 Q 5 1 S 4 5 S 1 6 Q 5 1 Q 1 5 C 1 C 2 C 3 C 4 C 5 C 6 */

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:153:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |  sf("%d%d",&n,&k);
      |    ^
servers.cpp:155:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   char c;sf(" %c",&c);
      |            ^
servers.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |    int a,b;sf("%d%d",&a,&b);
      |              ^
servers.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |    int a,b;sf("%d%d",&a,&b);
      |              ^
servers.cpp:167:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |    int a;sf("%d",&a);
      |            ^
#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...