Submission #1197975

#TimeUsernameProblemLanguageResultExecution timeMemory
1197975HappyCapybaraStations (IOI20_stations)C++17
0 / 100
3061 ms2162688 KiB
#include "stations.h" #include<bits/stdc++.h> using namespace std; int cnt; vector<int> in, out, d; vector<vector<int>> g; void dfs(int cur, int par){ d[cur] = d[par]+1; in[cur] = cnt; cnt++; for (int next : g[cur]){ if (next != par) dfs(next, cur); } out[cur] = cnt; cnt++; } vector<int> label(int n, int k, vector<int> u, vector<int> v){ g.resize(n); for (int i=0; i<n-1; i++){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } in.resize(n); out.resize(n); d.resize(n, -1); cnt = 0; dfs(0, 0); vector<int> res(n); map<int,int> m; for (int i=0; i<n; i++){ if (d[i] % 2) m[out[i]] = i; else m[in[i]] = i; } auto it = m.begin(); for (int i=0; i<n; i++){ res[it->second] = i; if (i != n-1) it++; } return res; } int find_next_station(int s, int t, vector<int> c){ if (c.size() == 1) return c[0]; int n = c.size(); if (s == 0){ for (int i=0; i<n; i++){ if (t <= c[i]) return c[i]; } } bool b = s < c[0]; if (b){ if (s < t && t < c[n-2]+1){ for (int i=0; i<n-1; i++){ if (t <= c[i]) return c[i]; } } else return c[n-1]; } else { if (c[1]-1 < t && t < s){ for (int i=n-1; i>=1; i--){ if (c[i] <= t) return c[i]; } } else return c[0]; } 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...