| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 578367 | SlavicG | 비스킷 담기 (IOI20_biscuits) | C++17 | 0 ms | 0 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 sz(a) (int)a.size()
const int N = 1000;
vector<int> adj[N];
int in[N], out[N], tt = 0, depth[N];
void dfs(int u, int par) {
in[u] = tt++;
for(int v: adj[u]) {
if(v == par) continue;
depth[v] = depth[u] ^ 1;
dfs(v, u);
}
out[u] = tt++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for(int i = 0; i < n; ++i) {
adj[i].clear();
tt = 0;
out[i] = 0, in[i] = 0;
}
for(int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1);
for (int i = 0; i < n; i++) {
labels[i] = (depth[i] ? out[i] : in[i]);
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int in_s, out_s;
bool dd = 0;
if(s == 0) {
in_s = 0;
out_s = c.back() + 1;
} else {
if(s < c[0]) {
dd = 0;
in_s = s;
if(sz(c) >= 2) out_s = c[sz(c) - 2] + 1;
else out_s = in_s;
} else {
dd = 1;
out_s = s;
if(sz(c) >= 2) in_s = c[1] - 1;
else in_s = out_s;
}
}
if(dd == 0) {
if(in_s <= t && t <= out_s) {
for(auto x: c) {
if(x >= t) return x;
}
} else return c.back();
} else {
if(in_s <= t && t <= out_s) {
reverse(c.begin(), c.end());
for(auto x: c) {
if(x <= t) return x;
}
} else return c[0];
}
}