제출 #209661

#제출 시각아이디문제언어결과실행 시간메모리
209661thebesMin-max tree (BOI18_minmaxtree)C++14
0 / 100
227 ms43712 KiB
#include <bits/stdc++.h> #define DEBUG 1 using namespace std; namespace output{ void __(short x){cout<<x;} void __(unsigned x){cout<<x;} void __(int x){cout<<x;} void __(long long x){cout<<x;} void __(unsigned long long x){cout<<x;} void __(double x){cout<<x;} void __(long double x){cout<<x;} void __(char x){cout<<x;} void __(const char*x){cout<<x;} void __(const string&x){cout<<x;} void __(bool x){cout<<(x?"true":"false");} template<class S,class T> void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");} template<class T> void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class S,class T> void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} void pr(){cout<<"\n";} template<class S,class... T> void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);} } using namespace output; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,char> pic; typedef pair<double,double> pdd; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vl; #define pb push_back #define fox(i,x,y) for(int i=(x);i<=(y);i++) #define foxr(i,x,y) for(int i=(y);i>=(x);i--) const int MN = 70005; int N, K, i, x, y, w, ds[MN], val[MN], dep[MN], par[MN], nxt, dn[2*MN], deg[MN]; int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);} vi adj[MN], g[2*MN]; pii ed[MN]; set<pii> st; map<pii,int> id, ans; struct qur{int x, y, w, id;}q[MN]; vector<qur> a, b; void dfs(int n,int p,int d){ dep[n] = d; par[n] = p; for(auto v : adj[n]){ if(v==p) continue; dfs(v, n, d+1); } } int main(){ scanf("%d",&N); for(i=1;i<N;i++){ scanf("%d%d",&x,&y); adj[x].pb(y); adj[y].pb(x); id[{min(x,y),max(x,y)}]=i; ed[i]={x,y}; } scanf("%d",&K); for(i=1;i<=K;i++){ char ch; scanf(" %c%d%d%d",&ch,&x,&y,&w); q[i]={x,y,w,N+i}; if(ch=='M') a.pb({x,y,w,N+i}); else b.pb({x,y,w,N+i}); } sort(a.begin(),a.end(),[](qur i,qur j){return i.w<j.w;}); sort(b.begin(),b.end(),[](qur i,qur j){return i.w>j.w;}); dfs(1, 0, 1); for(i=1;i<=N;i++) ds[i] = i; for(auto v : a){ x = fnd(v.x), y = fnd(v.y); while(x!=y){ if(dep[x]<dep[y]) swap(x,y); int cur = id[{min(x,par[x]),max(x,par[x])}]; g[v.id].pb(cur); g[cur].pb(v.id); ds[x] = fnd(par[x]); x = fnd(x); } } for(i=1;i<=N;i++) ds[i] = i; for(auto v : b){ x = fnd(v.x), y =fnd(v.y); while(x!=y){ if(dep[x]<dep[y]) swap(x,y); int cur = id[{min(x,par[x]),max(x,par[x])}]; g[v.id].pb(cur); g[cur].pb(v.id); ds[x] = fnd(par[x]); x = fnd(x); } } for(i=1;i<=K;i++) deg[N+i]=g[N+i].size(),assert(g[N+i].size()<=2); for(i=1;i<N;i++){ int res = 1<<30; assert(g[i].size()<=2); for(auto v : g[i]) res = min(res, deg[v]); st.insert({res, i}); val[i] = res; } while(st.size()){ int cur = st.begin()->second; st.erase(st.begin()); int ot = 0, hm = 1<<30; dn[cur] = 1; for(auto v : g[cur]){ if(!dn[v]&&deg[v]<hm){ ot = v; hm = deg[v]; } } if(!ot) continue; for(auto v : g[cur]){ if(!dn[v]&&v!=ot) deg[v]--; } ans[ed[cur]]=q[ot-N].w; dn[ot]=1; cur = ot; for(auto v : g[cur]){ if(dn[v]) continue; int res = 1<<30; for(auto u : g[v]){ if(!dn[v]) res=min(res,deg[v]); } st.erase({val[v], v}); val[v] = res; st.insert({val[v], v}); } } for(i=1;i<N;i++){ printf("%d %d %d\n",ed[i].first,ed[i].second,ans[ed[i]]); } return 0; }

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:141:22: warning: unused variable 'u' [-Wunused-variable]
             for(auto u : g[v]){
                      ^
minmaxtree.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:67: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:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&K);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d%d%d",&ch,&x,&y,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...