Submission #1236537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236537		SamAnd	Stations (IOI20_stations)	C++17	52.32 / 100	310 ms	600 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int timer;
int tin[N], tout[N];
vector <vector<int>> g;
void dfs(int v, int p) {
    tin[v] = ++timer;
    for (auto it : g[v]) {
        if (it == p) continue;
        dfs(it, v);
    }
    tout[v] = timer;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    timer = -1;
    g.clear();
    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]);
    }
    dfs(0, 0);
    vector <int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = tin[i] * 1000 + tout[i];
    }
    return ans;
}
int contains(int x, int y) {
    if (x / 1000 <= y / 1000 && x % 1000 >= y % 1000) return true;
    return false;
}
int find_next_station(int s, int t, vector<int> c) {
    if (contains(s, t)) {
        for (auto it : c) {
            if (contains(it, t) && contains(s, it)) return it;
        }
    }
    else {
        for (auto it : c) {
            if (!contains(s, it)) return it;
        }
    }
    assert(false);
}

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