| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 673708 | vjudge1 | 기지국 (IOI20_stations) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include "IOI20_Stations.h"
const int N = 1000;
int cnt=0;
std::vector<int> labels;
/*
clarifications:
k == n-1
c is sorted
Debugging:
- Idea => Proof
- Code => Accepted
*/
std::vector<std::vector<int>> g;
void dfs(int node, int par) {
labels[node] = cnt++;
for (int ch : g[node]) {
if (ch != par) {
dfs(ch, node);
}
}
labels[node] += N * (cnt++);
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
/*
1. Construct adjacency list
2. Label every node with its mrg(dt,ft)
*/
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]);
}
cnt = 0;
labels.clear();
labels.resize(n);
dfs(0, -1);
return labels;
}
/*
1. Now it's easy to find where to countinue the path
2. Tha path will be behined (i.e. the parent of current node), if the distinatin was greater than it
3. The path will be greater than or equal to any of the nighbours
4. If the distination was greater than or equals the node i, and less than any nighbour greater than i, then we need to go there
*/
int find_next_station(int s, int t, std::vector<int> c) {
int sz = c.size();
for (int i = 0; i < sz-1; i++) {
// The destination is under this child, Because it's impossible that it was discovered after that, or before that
if (t%N >= c[i]%N && t/N <= c[i+2]/N)
return c[i];
}
return c[sz - 1];
}