제출 #72974

#제출 시각아이디문제언어결과실행 시간메모리
72974yusufakeMin-max tree (BOI18_minmaxtree)C++98
100 / 100
807 ms61996 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define ll long long #define pp pair<int,int> const int N = 7e4 + 4; const int mod = 1e9 + 7; vector < pp > V[N],A[N],B[N]; unordered_map < int , vector<pp> > M; unordered_map < int , int > H,W; int ans[N],U[N],sz[N],T[N],Mn[N],Mx[N],C; void f(int x, int p, int n){ int h=1; sz[x] = 1; for(auto y : V[x]){ if(U[y.st] || y.st == p) continue; f(y.st,x,n); sz[x] += sz[y.st]; if(sz[y.st] > n/2) h=0; } if(h && n-sz[x] <= n/2) C=x; } void g(int x, int p, int roo){ T[x] = roo; for(auto y : V[x]){ if(U[y.st] || y.st == p) continue; g(y.st,x,roo); } } pp h(int x, int p, int i){ sz[x] = 1; int mn = 0; for(auto t : A[x]) if(T[t.st] && T[t.st] != T[x]) mn = max(mn , t.nd); int mx = mod; for(auto t : B[x]) if(T[t.st] && T[t.st] != T[x]) mx = min(mx , t.nd); pp a; for(auto y : V[x]){ if(U[y.st] || y.st == p) continue; a = h(y.st,x,y.nd); mn = max(mn , a.st); mx = min(mx , a.nd); sz[x] += sz[y.st]; } Mn[i] = max(Mn[i] , mn); Mx[i] = min(Mx[i] , mx); return mp(mn,mx); } void slv(int x, int n){ f(x,-1,n); x = C; U[x] = 1; T[x] = -1; for(auto y : V[x]){ if(U[y.st]) continue; g(y.st,x,y.st); } h(x,-1,0); g(x,-1,0); for(auto y : V[x]) if(!U[y.st]) slv(y.st,sz[y.st]); } void ff(int x){ H[x] = 1; for(auto y : M[x]){ if(H[y.st]) continue; ans[y.nd] = y.st; ff(y.st); } } void gg(int x, int p){ H[x] = 1; for(auto y : M[x]){ if(y.nd == p) continue; if(!H[y.st]) { ans[y.nd] = x; gg(y.st,y.nd); } else if(!ans[y.nd]) ans[y.nd] = x; } } int n,k,i,x,y,z,uu[N],vv[N],Z[N]; char c; int main(){ scanf("%d",&n); for(i=1;i<n;i++){ scanf("%d%d",&x,&y); V[x].pb(mp(y,i)); V[y].pb(mp(x,i)); Mx[i] = mod; uu[i] = x; vv[i] = y; } scanf("%d",&k); for(i=1;i<=k;i++){ scanf(" %c%d%d%d",&c,&x,&y,&z); Z[i] = z; if(c == 'm') { A[x].pb(mp(y,z)); A[y].pb(mp(x,z)); } else { B[x].pb(mp(y,z)); B[y].pb(mp(x,z)); } } slv(1,n); for(i=1;i<n;i++) if(Mn[i] != 0 || Mx[i] != mod){ M[ Mn[i] ].pb(mp(Mx[i],i)); M[ Mx[i] ].pb(mp(Mn[i],i)); W[ Mn[i] ]++; W[ Mx[i] ]++; } ff(0); ff(mod); for(i=1;i<=k;i++){ x = Z[i]; if(H[x]) continue; for(; W[x] == 1 ; x = z) { W[x]--; H[x] = 1; z = -1; for(auto y : M[x]){ W[y.st]--; if(W[y.st] > 0){ ans[y.nd] = x; z = y.st; } } } } for(i=1;i<=k;i++) if(!H[ Z[i] ]) gg(Z[i],0); for(i=1;i<n;i++) printf("%d %d %d\n", uu[i], vv[i], ans[i] ? ans[i] : Mx[i]); return 0; }

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d%d%d",&c,&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...