# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
683690 | sharaelong | Stations (IOI20_stations) | C++17 | 1049 ms | 760 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;
typedef pair<int, int> pii;
const int MAX_N = 1000;
vector<int> adj[MAX_N];
int tour_cnt = 0;
pii tour[MAX_N];
void dfs(int here, int parent = -1) {
tour[here].first = tour_cnt++;
for (int there: adj[here]) {
if (there != parent) {
dfs(there, here);
}
}
tour[here].second = tour_cnt-1;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
for (int i=0; i<n; ++i) adj[i].clear();
tour_cnt = 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);
assert(tour_cnt == n);
const int MAX_N = 1000;
vector<int> labels(n);
for (int i=0; i<n; i++) labels[i] = tour[i].first * MAX_N + tour[i].second;
// for (int i=0; i<n; ++i) cout << tour[i].first << ' ' << tour[i].second << endl;
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
const int MAX_N = 1000;
for (int i=0; i<c.size(); ++i) {
if (c[i] < s) {
assert(i == 0);
continue;
}
int x = c[i] / MAX_N, y = c[i] % MAX_N;
if (x <= t / MAX_N && t % MAX_N <= y) return c[i];
}
return c[0];
}
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... |