Submission #741789

#TimeUsernameProblemLanguageResultExecution timeMemory
741789rainliofficialStations (IOI20_stations)C++17
0 / 100
3031 ms2097152 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } #define sz(x) (int)x.size() #define all(x) begin(x), end(x) /* Date: 2023/05/14 14:06 Problem Link: Topic(s): Reflection: Solution Notes: We want to determine for two nodes (A, B), if A is an ancestor of B. Normally, an Euler tour can accomplish this. To encode the in and out times into one single number, we would need somewhere around 1000^2 + 1000 ~= 10^6 numbers. The next logical step is how to not encode the in and out times. Consider not storing BOTH the in and out for each node. Since we are given the neighbors, let p be the parent and c be some children, we can still determine if a node A within the subtree of p by checking the range [in[p], max(out[c])] . Consider storing everything an even depth away from the root to be in, and odd to be out. We know whether a node has in vs. out time by checking if it is even or odd. Now, we can compress down to 2*N states. We can reduce to N states by compressing the values, because only their relative sizes matter. We can determine if a node has the in time or out time by determining if: max(label of neighbor) > label[current] -> current has in time max(label of neighbor) < label[current] -> current has out time label[current] == 0 -> the root */ const int MAXN = 2e5+5, INF = 1e9; int n, in[MAXN], out[MAXN], dep[MAXN], timer = 0; vector<int> arr[MAXN]; void dfs(int at, int p, int d){ dep[at] = d; in[at] = timer++; for (int u : arr[at]){ if (u != p){ dfs(u, at, d+1); } } out[at] = timer++; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { vector<int> labels(n); for (int i=0; i<n-1; i++){ arr[u[i]].push_back(v[i]); arr[v[i]].push_back(u[i]); } dfs(0, -1, 0); for (int i=0; i<n; i++){ if (dep[i] % 2 == 0){ labels[i] = in[i]; }else{ labels[i] = out[i]; } } return labels; } int find_next_station(int s, int t, std::vector<int> c) { if (sz(c) == 0) return c[0]; if (s == c[0] + 1){ // s = in for (int i=0; i<(s == 0 ? sz(c) - 1 : sz(c)); i++){ if ((i == 0 ? s + 1 : c[i-1] + 1) <= t && c[i] >= t){ return i; } } assert(s != 0); return c[sz(c)-1]; // go to parent }else{ // s = out for (int i=(s == 0 ? 0 : 1); i<sz(c); i++){ if (t >= c[i] && t <= (i != sz(c) - 1 ? c[i+1]-1 : s - 1)){ return i; } } assert(s != 0); return c[0]; } return c[0]; } // int main(){ // cin.tie(0); ios_base::sync_with_stdio(0); // freopen("file.in", "r", stdin); // // freopen("file.out", "w", stdout); // }
#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...