Submission #1156718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156718		lightentheshadow	Stations (IOI20_stations)	C++20	0 / 100	3053 ms	2162688 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1005];
int timeIn[1005], timeOut[1005], depth[1005], timeDfs = 0;
void dfs(int u, int pre) {
    timeIn[u] = timeDfs++;
    for (auto v: adj[u]) {
        if (v == pre) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
    timeOut[u] = timeDfs;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i = 0; i < n; i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

	vector<int> labels(n);
    dfs(0, 0);

    vector<int> save;
    for (int i = 0; i < n; i++)
        if (depth[i] % 2) labels[i] = timeOut[i];
            else labels[i] = timeIn[i];

    save = labels;
    sort(save.begin(), save.end());
    for (int i = 0; i < n; i++)
        labels[i] = lower_bound(save.begin(), save.end(), labels[i]) - save.begin();

	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if (c.size() == 1) return c[0];

    int ans = -1;
    if (s > c.back()) {
        int par = c[0];
        if (t < c[1] || s <= t) return par;
        int x = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
        ans = c[x];
    }
    else {
        int par = c.back();
        if (s >= t || s > c[c.size() - 2]) return par;
        int x = lower_bound(c.begin(), c.end(), t) - c.begin();
        ans = c[x];
    }

    return ans;
}

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