Submission #487230

#TimeUsernameProblemLanguageResultExecution timeMemory
487230niloyrootRigged Roads (NOI19_riggedroads)C++14
0 / 100
215 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<ll>; using pl = pair<ll,ll>; #define pb push_back #define form(m,it) for(auto it=m.begin(); it!=m.end(); it++) #define forp(i,a,b) for(ll i=a; i<=b; i++) #define forn(i,a,b) for(ll i=a; i>=b; i--) #define newl '\n' const ll mod = 1000000007; void solve(){ ll n,e; cin>>n>>e; vector<pl> edg; ll a,b; forp(i,1,e){ cin>>a>>b; edg.pb({a,b}); } vector<pl> adj[n+1]; bool mst[e+1]={0}; forp(i,1,n-1){ ll t; cin>>t; t--; mst[t]=1; a=edg[t].first; b=edg[t].second; adj[a].pb({b,t}); adj[b].pb({a,t}); } ll len[n+1]; pl par[n+1]; function<void(ll,ll)> dfs = [&](ll i, ll pa){ for(auto u:adj[i]){ if(u.first!=pa){ len[u.first]=len[i]+1; par[u.first].first=i; par[u.first].second=u.second; dfs(u.first,i); } } }; len[1]=0; par[1].first=-1; par[1].second=-1; dfs(1,-1); ll cnt=1; ll ans[e]={0}; forp(i,0,e-1){ if(mst[i]){ if(!ans[i]){ ans[i]=cnt; cnt++; } } else { vi cyc; a=edg[i].first; b=edg[i].second; if(len[a]<len[b]){swap(a,b);} while(len[a]!=len[b]){ if(!ans[par[a].second]){ cyc.pb(par[a].second); } a=par[a].first; } while(a!=b){ if(!ans[par[b].second]){ cyc.pb(par[b].second); } if(!ans[par[a].second]){ cyc.pb(par[a].second); } a=par[a].first; b=par[b].first; } sort(cyc.begin(), cyc.end()); for(auto ed:cyc){ ans[ed]=cnt; cnt++; } ans[i]=cnt; cnt++; } cout<<ans[i]<<" "; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output3.txt","w",stdout); #endif int t=1; //cin>>t; while(t--)solve(); }

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen("output3.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...