#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] = 1;
for(int i: adj[c]) {
if(i == pr) continue;
dfs(i, c);
sz[c] += sz[i];
}
}
vector<int> euler_tree() {
id = 0;
dfs(0, -1);
vector<int> ans(n);
for(int i = 0; i < n; i ++) {
sz[i] --;
ans[i] = ids[i]*1000+sz[i];
assert(ids[i]< 1000);
assert(sz[i]<1000);
}
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() {
nddds.clear();
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 j = 0; j < n; j ++) {
ans[nds[j]] = j;
}
return ans;
}
}
return vector<int>();
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) {
int sid = s/1000, ssz = s%1000;
int tid = t/1000, tsz = t%1000;
if(sid <= tid && tid <= sid + ssz) {
for(int i: c) {
int nid = i/1000, nsz = i%1000;
if(nid <= tid && tid <= nid + nsz) {
return i;
}
}
assert(0);
}
for(int i: c) {
int nsz = i%1000;
if(nsz >= ssz) {
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);
}
// int main() {
// int nv, nk;
// cin >> nv >> nv >> nk;
// vector<int> u, v;
// vector<int> ptss[N];
// for(int i = 1; i < nv; i ++) {
// int a, b;
// cin >> a >> b;
// u.push_back(a);
// v.push_back(b);
// ptss[a].push_back(b);
// ptss[b].push_back(a);
// }
// vector<int> lb = label(nv, nk, u, v);;
// for(int i: lb) cout << i << " ";
// // int q;
// // cin >> q;
// // while(q--) {
// // int a, b, c;
// // cin >> a >> b >> c;
// // vector<int> adjs;
// // for(int i: ptss[a]) {
// // adjs.push_back(lb[i]);
// // }
// // cout << find_next_station(lb[a], lb[b], adjs) << " ";
// // }
// }
Compilation message
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:65:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
65 | if(u[i] == i+1 && v[i] == i/2 || u[i] == i/2 && v[i] == i+1) continue;
stations.cpp: In function 'int findEuler(int, int, std::vector<int>)':
stations.cpp:79:20: warning: unused variable 'tsz' [-Wunused-variable]
79 | int tid = t/1000, tsz = t%1000;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
374 ms |
924 KB |
Output is correct |
| 2 |
Correct |
283 ms |
924 KB |
Output is correct |
| 3 |
Correct |
561 ms |
696 KB |
Output is correct |
| 4 |
Correct |
431 ms |
684 KB |
Output is correct |
| 5 |
Correct |
413 ms |
684 KB |
Output is correct |
| 6 |
Correct |
306 ms |
920 KB |
Output is correct |
| 7 |
Correct |
277 ms |
684 KB |
Output is correct |
| 8 |
Correct |
1 ms |
764 KB |
Output is correct |
| 9 |
Correct |
4 ms |
768 KB |
Output is correct |
| 10 |
Correct |
1 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
628 ms |
1012 KB |
Output is correct |
| 2 |
Correct |
510 ms |
824 KB |
Output is correct |
| 3 |
Correct |
588 ms |
684 KB |
Output is correct |
| 4 |
Correct |
525 ms |
684 KB |
Output is correct |
| 5 |
Correct |
506 ms |
684 KB |
Output is correct |
| 6 |
Correct |
625 ms |
824 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 |
581 ms |
684 KB |
Output is correct |
| 2 |
Incorrect |
421 ms |
852 KB |
Wrong query response. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
361 ms |
948 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
