# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
590105 | almothana05 | Stations (IOI20_stations) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "stations.h"#include <vector>#include <bits/stdc++.h>using namespace std;vector<int> gr[2000] , num , de ;int vis[2000];int pl = -1;void dfs(int x , int cmp){ de.push_back(x); vis[x] = 1; // cout << x << ' ' << cmp << "\n"; pl++; if(cmp == 0){ num[x] = pl; } // cout << 1 << ' '; for(int i = 0 ; i< gr[x].size() ; i++){ int kind = gr[x][i]; if(vis[kind] == 0){ dfs(kind , cmp ^ 1); } } pl++; // assert(pl > 0); if(cmp == 1){ num[x] = pl; } while(num[x] == -1);}vector<int> label(int menge, int maxi, vector<int> u, vector<int> v) { num.clear(); de.clear(); for(int i = 0 ; i < 1000 ; i++){ gr[i].clear(); vis[i] = 0; } pl = -1; num.resize(menge , -1); for(int i = 0 ; i < menge - 1 ; i++){ gr[u[i]].push_back(v[i]); gr[v[i]].push_back(u[i]); } for(int i = 0 ; i < menge ; i++){ if(vis[i] == 0){ dfs(i , 0); } // while(num[i] == -1); } assert(de.size() == menge); for(int i = 0 ; i < menge ; i++){ // cout << num[i] << ' '; // assert(num[i] >= 0); } // cout << "\n"; return num;} int find_next_station(int s, int t, vector<int> c) { int be , en , erg = -1; if(s < c[0]){ be = s; for(int i = 0 ; i < c.size() - 1 ; i++){ en = c[i]; if(be <= t && t <= en){ return c[i]; } be = c[i]; } return c[c.size() - 1]; } else{ c.push_back(s); for(int i = 1 ; i < c.size() - 1 ; i++){ be = c[i]; en = c[i + 1] - 1; if(be <= t && t <= en){ return c[i]; } } return c[0]; }}