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 N 1005
vector<int> adj[N];
int n, ids[N], sz[N], id;
void dfs(int c, int pr) {
ids[c] = id++;
sz[c] = 0;
for(int i: adj[c]) {
if(i == pr) continue;
dfs(i, c);
sz[c] += sz[i] + 1;
}
}
vector<int> euler_tree() {
id = 0;
dfs(0, -1);
vector<int> ans(n);
for(int i = 0; i < n; i ++) {
ans[i] = ids[i]*1000+sz[i];
}
return ans;
}
vector<int> flatten() {
for(int i = 0; i < n; i ++) {
if(adj[i].size() == 1) {
vector<int> nds(1,i);
int pr = i, c = adj[i][0];
while(adj[c].size() != 1) {
nds.push_back(c);
if(pr == adj[c][0]) {
swap(pr, c);
c = adj[pr][1];
} else {
swap(pr, c);
c = adj[pr][0];
}
}
nds.push_back(c);
vector<int> ans(n);
for(int i = 0; i < n; i ++) {
ans[nds[i]] = i;
}
return nds;
}
}
assert(0);
}
std::vector<int> label(int ngb, int k, std::vector<int> u, std::vector<int> v) {
n = ngb;
for(auto&i: adj) i.clear();
for(int i = 0; i < n-1; i ++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int ms = 0;
for(auto&i: adj) ms = max(ms, (int)i.size());
if(k >= 1000000) {
return euler_tree();
}
for(int i = 0; i < n-1; i ++) {
if(u[i] == i+1 && v[i] == i/2 || u[i] == i/2 && v[i] == i+1) continue;
return flatten();
}
vector<int> nds;
for(int i = 0; i < n; i ++) nds.push_back(i);
return nds;
}
struct Nd {
int id, sz;
Nd(int i) : id(i/1000), sz(i%1000) {
}
};
int findEuler(int s, int t, vector<int> c) {
Nd cur = Nd(s), nxt = Nd(t);
if(nxt.id >= cur.id && nxt.id <= cur.id+cur.sz) {
for(int i: c) {
Nd it = Nd(i);
if(nxt.id >= it.id && nxt.id <= it.id+it.sz) {
return i;
}
}
assert(0);
}
for(int i: c) {
Nd it = Nd(i);
if(it.sz >= cur.sz) {
return i;
}
}
assert(0);
}
int findFlat(int s, int t, vector<int> c) {
if(s < t) {
if(c.size() == 1) return c[0];
return c[1];
} else {
return c[0];
}
}
int ds[N], pr[N];
int findWeird(int s, int t, vector<int> c) {
for(auto&i: adj) i.clear();
for(int i = 0; i < max(s,t); i ++) {
adj[i+1].push_back(i/2);
adj[i/2].push_back(i+1);
}
for(auto&i: ds) i = N;
queue<int> que;
que.push(t); ds[t] = 0; pr[t] = 0;
while(que.size()) {
int c = que.front(); que.pop();
for(int i: adj[c]) {
if(ds[i] > ds[c]+1) {
ds[i] = ds[c]+1;
pr[i] = c;
que.push(i);
}
}
}
return pr[s];
}
int find_next_station(int s, int t, std::vector<int> c) {
int mv = max(s, t);
for(int i: c) mv = max(mv, i);
if(mv >= 1000) {
return findEuler(s,t,c);
}
if(c.size() == 1 && (c[0] == s+1 || c[0] == s-1)) {
return findFlat(s,t,c);
}
if(c.size() == 2 && c[0] == s-1 && c[1] == s+1) {
return findFlat(s,t,c);
}
return findWeird(s,t,c);
}
Compilation message (stderr)
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:63:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
63 | if(u[i] == i+1 && v[i] == i/2 || u[i] == i/2 && v[i] == i+1) continue;
# | 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... |