Submission #741793

#	Time	Username	Problem	Language	Result	Execution time	Memory
741793		rainliofficial	Stations (IOI20_stations)	C++17	0 / 100	3040 ms	2097152 KiB

stations

#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];
        }
    }
    // for (int i : labels) cout << i << " ";
    // cout << "\n";
	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]){
        // 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 c[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 c[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);
    
// }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61