#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> nddds;
void DFS(int c, int pr) {
nddds.push_back(c);
for(int i: adj[c]) {
if(i == pr) continue;
DFS(i, c);
}
}
vector<int> flatten() {
for(int i = 0; i < n; i ++) {
if(adj[i].size() == 1) {
DFS(i, -1);
vector<int> nds = nddds;
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
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:60:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
60 | if(u[i] == i+1 && v[i] == i/2 || u[i] == i/2 && v[i] == i+1) continue;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Invalid length of array as the response of 'label'. scenario=1, n=3, len=13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
660 ms |
1020 KB |
Output is correct |
| 2 |
Correct |
504 ms |
824 KB |
Output is correct |
| 3 |
Correct |
574 ms |
680 KB |
Output is correct |
| 4 |
Correct |
542 ms |
684 KB |
Output is correct |
| 5 |
Correct |
521 ms |
684 KB |
Output is correct |
| 6 |
Correct |
625 ms |
828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
363 ms |
948 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
572 ms |
688 KB |
Output is correct |
| 2 |
Incorrect |
436 ms |
684 KB |
Wrong query response. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
353 ms |
960 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
