# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
682021 | junkbot | Stations (IOI20_stations) | C++14 | 884 ms | 1356 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define D(x...) fprintf(stderr, x)
#define D(x...)
const int MAX_N = 1005;
const int UNLABELLED = -1;
const int PENDING = -2;
struct Solve {
int upto;
vector<vector<int>> adjlist;
vector<int> labels;
Solve(int n, vector<int> u, vector<int> v) : upto(0), adjlist(n), labels(n) {
for (auto i=0;i<u.size();i++) {
adjlist[u[i]].push_back(v[i]);
adjlist[v[i]].push_back(u[i]);
}
fill(labels.begin(), labels.end(), UNLABELLED);
}
// label everything in u's subtree.
void go(int u, bool isPre) {
if (labels[u] != UNLABELLED) return;
labels[u] = PENDING;
if (isPre) labels[u] = getNext();
for (auto v: adjlist[u]) go(v, !isPre);
if (!isPre) labels[u] = getNext();
}
int getNext() {
int ret = upto;
upto++;
return ret;
}
};
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
auto solver = new Solve(n, u, v);
solver->go(0, true);
vector<int> ret;
for (auto l: solver->labels) {
ret.push_back(l);
}
D("labels:");
for (auto l: solver->labels) {
D(" %d", l);
}
D("\n");
return ret;
}
int find_next_station(int s, int t, std::vector<int> c) {
if (s < c.front()) {
// preorder
int left_exclusive = s;
for (auto i=0;i<c.size()-1;i++) {
auto l = c[i];
if (left_exclusive < t && t <= l) return l;
left_exclusive = l;
}
return c.back();
} else {
// postorder
int right_exclusive = s;
for (auto i=c.size()-1;i>0;i--) {
auto l = c[i];
if (l <= t && t < right_exclusive) return l;
right_exclusive = l;
}
return c.front();
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |