# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
430749 | 2021-06-17T03:27:52 Z | JUANDI321 | Stations (IOI20_stations) | C++17 | 0 ms | 0 KB |
#include "stations.h" #include <vector> #include <iostream> #include <cstring> using namespace std; vector<vector<int>> g(1000+10); vector<int> l(10000 +10); bool ch[1010]; int r == 0; void dfs(int node, int i) { if(ch[node])return; ch[node]=true; l[i] = node; //cout<<node<<endl; for(int y : g[node]) { if(!ch[y]) { dfs(y, i+1); } } } vector<int> label(int n, int k, vector<int> u, vector<int> v) { r++; vector<int> labels(n); for(int i = 0; i < n-1; i++) { g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } int spn = 0, c = 0; for(int i = 0; i < n; i++) { if(g[i].size() == 1) { c++; if((r == 1 && c ==1) || (r==2 && c==2)) { spn = i; break; } } } dfs(spn, 0); //cout<<"hola"<<endl; for (int i = 0; i < n; i++) { labels[l[i]] = i; //cout<<"l[i] "<<l[i]<<" lb i "<<labels[l[i]]<<endl; } //cout<<"---------"<<endl; memset(ch, false, sizeof(ch)); for(int i=0; i<n; i++) g[i].clear(); l.clear(); return labels; } int find_next_station(int s, int t, vector<int> c) { if(t>s)return s+1; return s-1; }