제출 #530481

#제출 시각아이디문제언어결과실행 시간메모리
530481azberjibiouInside information (BOI21_servers)C++17
100 / 100
544 ms65232 KiB
#include <bits/stdc++.h> #define gibon ios::sync_with_stdio(false); cin.tie(0); #define fir first #define sec second #define pii pair<int, int> #define pll pair<ll, ll> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") typedef long long ll; using namespace std; int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0}; const int mxN=120005; const int mxM=1010; const int mxK=105; const int MOD=1000000007; const ll INF=1e15; const ll P1=1000000007; const ll P2=1000000009; typedef struct query{ char typ; int s, e; }edge; int N, K; vector <pii> vadj[mxN], eadj[mxN]; vector <int> echild[mxN]; query Q[2*mxN]; int vpar[mxN], vsps[20][mxN], vdep[mxN]; int edep[mxN], cursum[mxN], esps[20][mxN]; int g[mxN]; int sub[mxN]; int in[mxN], out[mxN], eidx; int ntime; void dfsv0(int now, int pre) { for(pii ele : vadj[now]) if(ele.fir!=pre) { vdep[ele.fir]=vdep[now]+1; vpar[ele.fir]=ele.sec; vsps[0][ele.fir]=now; dfsv0(ele.fir, now); } } void dfse0(int now, int pre) { sub[now]=1; for(pii ele : eadj[now]) if(ele.fir!=pre) { echild[now].push_back(ele.fir); esps[0][ele.fir]=now; edep[ele.fir]=edep[now]+1; cursum[ele.fir]+=cursum[now]+ele.sec; dfse0(ele.fir, now); sub[now]+=sub[ele.fir]; } for(int i=1;i<echild[now].size();i++) { if(sub[echild[now][0]]<sub[echild[now][i]]) swap(echild[now][0], echild[now][i]); } } void dfse1(int now) { in[now]=++eidx; if(echild[now].empty()) return; g[echild[now][0]]=g[now]; for(int i=1;i<echild[now].size();i++) g[echild[now][i]]=echild[now][i]; for(int ele : echild[now]) dfse1(ele); out[now]=eidx; } void solvN1() { for(int i=0;i<N+K;i++) { if(Q[i].typ=='C') cout << 1 << '\n'; if(Q[i].typ=='Q') cout << "yes" << '\n'; } } int solv_lca(int a, int b, int sps[][mxN], int *dep) { if(dep[a]<dep[b]) swap(a, b); for(int i=19;i>=0;i--) { if(dep[a]>=dep[b]+(1<<i)) a=sps[i][a]; } if(a==b) return a; for(int i=19;i>=0;i--) if(sps[i][a]!=sps[i][b]) a=sps[i][a], b=sps[i][b]; return sps[0][a]; } int vdown_edge(int s, int e) { for(int i=19;i>=0;i--) if(vdep[s]>vdep[e]+(1<<i)) s=vsps[i][s]; return s; } ll seg[4*mxN], lazy[4*mxN]; void propagate(int idx, int s, int e) { int mid=(s+e)/2; seg[2*idx]+=(mid-s+1)*lazy[idx]; seg[2*idx+1]+=(e-mid)*lazy[idx]; lazy[2*idx]+=lazy[idx]; lazy[2*idx+1]+=lazy[idx]; lazy[idx]=0; } void seg_upd(int idx, int s1, int e1, int s2, int e2) { if(s1>e2 || s2>e1) return; if(s2<=s1 && e1<=e2) { seg[idx]+=e1-s1+1; lazy[idx]++; return; } propagate(idx, s1, e1); int mid=(s1+e1)/2; seg_upd(2*idx, s1, mid, s2, e2); seg_upd(2*idx+1, mid+1, e1, s2, e2); seg[idx]=seg[2*idx]+seg[2*idx+1]; } int seg_solv(int idx, int s1, int e1, int s2, int e2) { if(s2>e1 || s1>e2) return 0; if(s2<=s1 && e1<=e2) return seg[idx]; propagate(idx, s1, e1); int mid=(s1+e1)/2; return seg_solv(2*idx, s1, mid, s2, e2)+seg_solv(2*idx+1, mid+1, e1, s2, e2); } void hld_upd(int s, int e) { while(edep[g[s]]>edep[e]) { seg_upd(1, 1, N-1, in[g[s]], in[s]); s=esps[0][g[s]]; } seg_upd(1, 1, N-1, in[e], in[s]); } int hld_solv(int s, int e) { int ret=0; while(edep[g[s]]>edep[e]) { ret+=seg_solv(1, 1, N-1, in[g[s]], in[s]); s=esps[0][g[s]]; } ret+=seg_solv(1, 1, N-1, in[e], in[s]); return ret; } int solvC(int now) { int enow=vadj[now][0].sec; int npar=enow; for(int i=19;i>=0;i--) { if(esps[i][npar]!=0 && cursum[esps[i][npar]]==cursum[enow]) npar=esps[i][npar]; } return hld_solv(enow, npar); } bool esolvQ(int now, int data) { //printf("now=%d, data=%d\n", now, data); //printf("ntime=%d\n", ntime); if(now==data) return (now<=ntime); int elca=solv_lca(now, data, esps, edep); return (cursum[data]==cursum[elca] && cursum[elca]-cursum[now]==edep[elca]-edep[now] && now<=ntime); } bool solvQ(int now, int data) { if(now==data) return true; int vlca=solv_lca(now, data, vsps, vdep); if(vlca==now) { return esolvQ(vpar[vdown_edge(data, now)], vpar[data]); } else if(vlca==data) { return esolvQ(vpar[now], vpar[vdown_edge(now, data)]); } else { return esolvQ(vpar[now], vpar[data]); } } void eupd(int now) { int npar=now; for(int i=19;i>=0;i--) { if(esps[i][npar]!=0 && cursum[esps[i][npar]]-cursum[npar]==edep[esps[i][npar]]-edep[npar]) npar=esps[i][npar]; } hld_upd(now, npar); } int main() { gibon cin >> N >> K; int idx=1; for(int i=0;i<N+K-1;i++) { cin >> Q[i].typ; if(Q[i].typ=='C') cin >> Q[i].s; else cin >> Q[i].s >> Q[i].e; if(Q[i].typ=='S') { vadj[Q[i].s].emplace_back(Q[i].e, idx); vadj[Q[i].e].emplace_back(Q[i].s, idx); idx++; } } if(N==1) { solvN1(); return 0; } for(int i=1;i<=N;i++) { if(vadj[i].size()) sort(vadj[i].begin(), vadj[i].end(), [](pii a, pii b){return a.sec<b.sec;}); for(int j=0;j+1<vadj[i].size();j++) { eadj[vadj[i][j].sec].emplace_back(vadj[i][j+1].sec, 1); eadj[vadj[i][j+1].sec].emplace_back(vadj[i][j].sec, 0); } } dfsv0(1, -1); for(int i=1;i<20;i++) for(int j=1;j<=N;j++) vsps[i][j]=vsps[i-1][vsps[i-1][j]]; g[1]=1; dfse0(1, -1); dfse1(1); for(int i=1;i<20;i++) for(int j=1;j<=N;j++) esps[i][j]=esps[i-1][esps[i-1][j]]; /*for(int i=1;i<N;i++) { printf("i=%d: ", i); for(auto ele : eadj[i]) printf("(%d, %d) ", ele.fir, ele.sec); printf("\n"); } for(int i=1;i<N;i++) printf("in[%d]=%d\n", i, in[i]); for(int i=1;i<N;i++) printf("g[%d]=%d\n", i, g[i]);*/ for(int i=0;i<N+K-1;i++) { if(Q[i].typ=='S') { ntime++; eupd(ntime); } if(Q[i].typ=='C') { cout << solvC(Q[i].s)+1 << '\n'; } if(Q[i].typ=='Q') { cout << (solvQ(Q[i].s, Q[i].e) ? "yes" : "no") << '\n'; } } }

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void dfse0(int, int)':
servers.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=1;i<echild[now].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'void dfse1(int)':
servers.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=1;i<echild[now].size();i++)  g[echild[now][i]]=echild[now][i];
      |                 ~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:217:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for(int j=0;j+1<vadj[i].size();j++)
      |                     ~~~^~~~~~~~~~~~~~~
#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...