Submission #1186294

#TimeUsernameProblemLanguageResultExecution timeMemory
1186294SwanStations (IOI20_stations)C++20
0 / 100
299 ms600 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> #include <stack> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <climits> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <optional> //#define int long long #define INP freopen("subrev.in","r",stdin) #define OUTP freopen("subrev.out","w",stdout) using ld = long double; using LD = ld; using namespace std; const int maxn = 1200; vector<vector<int> > v; int lab[maxn]; int sz[maxn]; void dfs1(int u, int p = -1) { sz[u] = 1; for (auto a : v[u]) { if (a == p) continue; dfs1(a, u); sz[u] += sz[a]; } } int cur = 1; void dfs2(int u, bool isMin = true, int p = -1) { if (isMin || (p != -1 && v[u].size() == 1)) { lab[u] = cur++; } else { lab[u] = cur + sz[u] - 1; } if ((p != -1 && v[u].size() == 1)) return; for (auto a : v[u]) { if (a == p) continue; dfs2(a, !isMin, u); } if (!isMin) { cur++; } } int find_next_station(int s, int t, vector<int> c) { if (c.size() == 1) return c[0]; if (s < c[0]) { int last = s + 1; for (int i = 0; i < c.size() - 1; i++) { if (c[i] == last ){ if (c[i] == t) return c[i]; else { last++; continue; } } int r = c[i] - 1; if (t >= last && t <= r) return c[i]; last = c[i] + 1; } return c.back(); } else { int r = s - 1; for (int i = c.size() - 1; i > 0; i--) { if (c[i] == r) { if (c[i] == t) return c[i]; else { r--; continue; } } int l = c[i] + 1; cout << "WOW " << l << ' ' << r << endl; if (t >= l && t <= r) return c[i]; r = c[i] - 1; } return c[0]; } } vector<int> label(int n, int k, vector<int> a, vector<int> b) { v.clear(); v.resize(a.size() + 10); cur = 1; for (int i = 0; i < a.size() + 10; i++) { sz[i] = 0; lab[i] = 0; } for (int i = 0; i < a.size(); i++) { v[a[i]].push_back(b[i]); v[b[i]].push_back(a[i]); } dfs1(0); dfs2(0); vector<int> res; for (int i = 0; i < a.size() + 1; i++) res.push_back(lab[i]); return res; } /* void solve() { vector<int> res = label(12, 12, {0, 0, 0, 2, 2, 2, 8, 8, 8, 3, 4}, {1, 2, 3, 6, 7, 8, 9, 10, 11, 4, 5}); cout << find_next_station(10, 11, {11, 12}); } int main() { ios_base::sync_with_stdio(0); solve(); } */
#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...