Submission #1064797

#TimeUsernameProblemLanguageResultExecution timeMemory
1064797XJP12Stations (IOI20_stations)C++14
5 / 100
644 ms940 KiB
#include <bits/stdc++.h> #include "stations.h" using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; vvi g; vi vis; vi l; vi indeg; int y=-1; int cont=0; void dfs1(int u, int p){ // cout<<u<< " "; vis[u]=true; if(u==y){ l[u]=10000+l[p]; }else{ l[u]=cont; cont++; } for(auto v: g[u]){ if(!vis[v]){ dfs1(v,u); } } } void dfs(int u){ vis[u]=true; l[u]=cont; cont++; for(auto v: g[u]){ if(!vis[v]){ dfs(v); } } } vi label(int n, int k, vi u, vi v) { l.assign(n,0); vis.assign(n,0); indeg.assign(n,0); g.assign(n, vi()); y=-1; cont=0; for(int i=0; i<n-1; i++){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); indeg[u[i]]++; indeg[v[i]]++; } vi x; for(int i=n-1; i>=0; i--){ if(indeg[i]==1) x.push_back(i); if(indeg[i]==3) y=i; // cout<<x<<y<<endl; } if(k>1000 && y!=-1){ int a=g[y][0], b = g[y][1], c=g[y][2]; int x1=-1; for(int i=0; i<(int)x.size(); i++){ if(x[i]!=a && x[i]!=b && x[i]!=c){ x1=x[i]; }else{ if(x[i]==a) y=a; if(x[i]==b) y=b; if(x[i]==c) y=c; } } // cout<<y<<endl; if(x1==-1){ if(y!=a){ x1=a; }else{ x1=b; } } dfs1(x1,x1); }else{ dfs(x[0]); } return l; } int find_next_station(int s, int t, vi c) { // return 0; int size = (int)c.size(); if(size==1)return c[0]; for(int i=0; i<size; i++){ if(c[i]==t) return c[i]; } if(s<=10000 && t<=10000){ if(t>s){ return c[1]; }else{ return c[0]; } }else{ if(t-10000>s){ return c[1]; }else{ return c[0]; } } }
#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...