Submission #555392

#TimeUsernameProblemLanguageResultExecution timeMemory
555392new_accMin-max tree (BOI18_minmaxtree)C++14
29 / 100
152 ms35852 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; const int N=1e5+10; const int SS=1<<19; const int INFi=2e9; const ll INFl=1e13; const ll mod2=998244353; const ll mod=1e9+7; const ll mod3=1000696969; const ll p=70032301; const ull p2=913; const int L=18; int t[N],match[(N<<1)],pod[N],val[N],oj[N],ans[N]; pair<int,int>przedzial[N],w[N]; vi g[N],graf[N],graf2[(N<<1)]; bool vis[(N<<1)]; unordered_map<int,int>num; void add(int x,set<int>* s){ auto it=s->lower_bound(x); if(it!=(s->end()) and *it==x) (*s).erase(x); else (*s).insert(x); } set<int>* dfs(int v,int o,int p){ oj[v]=o; pod[v]=1; vector<set<int>* >curr; int maxi=0,byl=0; for(auto u:graf[v]){ if(u==o) continue; set<int>* a=dfs(u,v,p); curr.push_back(a); pod[v]+=pod[u]; maxi=max(maxi,pod[u]); } set<int>* pom; int k=-1; for(auto u:graf[v]){ if(u==o) continue; k++; if(maxi==pod[u] and !byl){ byl=1; pom=curr[k]; } } byl=0,k=-1; for(auto u:graf[v]){ if(u==o) continue; k++; if(maxi==pod[u] and !byl){ byl=1; continue; } for(auto x:(*curr[k])) add(x,pom); } if(maxi==0) pom=new set<int>; for(auto u:g[v]) add(u,pom); if(p){ if(pom->size()) przedzial[v].fi=*(pom->begin()); else przedzial[v].fi=-1; }else{ if(pom->size()){ auto it=pom->end(); it--; przedzial[v].se=*it; }else przedzial[v].se=-1; } return pom; } bool dfs2(int v){ vis[v]=1; for(auto u:graf2[v]){ if(!match[u]){ match[u]=v,match[v]=u; return 1; } } for(auto u:graf2[v]){ if(!vis[match[u]] and dfs2(match[u])){ match[v]=u,match[u]=v; return 1; } } return 0; } void solve(){ int n; cin>>n; for(int a,b,i=1;i<n;i++){ cin>>a>>b; graf[a].push_back(b),graf[b].push_back(a); } int m; cin>>m; for(int a,b,c,i=1;i<=m;i++){ char xd; cin>>xd>>a>>b>>c; num[c]=i; if(xd=='m') g[a].push_back(c),g[b].push_back(c); else a*=-1; w[i]={a,b},val[i]=c; } dfs(1,1,1); for(int i=1;i<=n;i++) g[i].clear(); for(int i=1;i<=m;i++){ if(w[i].fi<0) g[w[i].fi*(-1)].push_back(val[i]),g[w[i].se].push_back(val[i]); } dfs(1,1,0); //for(int i=1;i<=n;i++) cout<<przedzial[i].fi<<" "<<przedzial[i].se<<"\n"; for(int i=2;i<=n;i++){ if(przedzial[i].fi!=-1) graf2[i].push_back(num[przedzial[i].fi]+n), graf2[num[przedzial[i].fi]+n].push_back(i); if(przedzial[i].se!=-1) graf2[i].push_back(num[przedzial[i].se]+n), graf2[num[przedzial[i].se]+n].push_back(i); } while(true){ bool b=0; for(int i=2;i<=n;i++) if(!vis[i] and !match[i] and dfs2(i)) b=1; for(int i=1;i<=n+m;i++) vis[i]=0; if(!b) break; } for(int i=2;i<=n;i++){ if(przedzial[i].fi==-1 and przedzial[i].se==-1) ans[i]=0; else{ if(przedzial[i].fi!=-1) ans[i]=przedzial[i].fi; else ans[i]=przedzial[i].se; } } for(int i=1;i<=m;i++) ans[match[i+n]]=val[i]; for(int i=2;i<=n;i++) cout<<i<<" "<<oj[i]<<" "<<ans[i]<<"\n"; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int tt=1; while(tt--) solve(); }

Compilation message (stderr)

minmaxtree.cpp: In function 'std::set<int>* dfs(int, int, int)':
minmaxtree.cpp:60:35: warning: 'pom' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |         for(auto x:(*curr[k])) add(x,pom);
      |                                ~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...