#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(c) (c.begin()), (c.end())
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define csz(c) ((int)c.size())
#include "stations.h"
const int maxn = 1e3 + 5;
vi g[maxn];
int st[maxn]; int en[maxn]; int d[maxn]; int dt = -1;
void dfs(int c, int p=-1, int dd=0) {
st[c] = ++dt;
d[c] = dd;
for(auto e : g[c]) {
if(e!=p) {
dfs(e, c, dd+1);
}
}
en[c] = ++dt;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
rep(i, n-1) {
g[u[i]].pb(v[i]); g[v[i]].pb(u[i]);
}
dfs(0);
vi res(n);
rep(i, n) {
if(d[i]%2) {
res[i] = en[i];
} else {
res[i] = st[i];
}
}
/*cout << "debug" << endl;
rep(i, n) {
cout << st[i] << ' '<< en[i] << endl;
}
for(auto e : res) {
cout << e << ' ';
}
cout << endl;
*/
rep(i, n) {
g[i].clear(); st[i] = 0; en[i] = 0; d[i] = 0;
}
dt = -1;
return res;
}
const int base = 2004;
int find_next_station_bad(int s, int t, std::vector<int> c) {
int s_st = s % base;
int t_st = t % base;
int s_en = s / base;
int t_en = t / base;
vi childs;
int best = 0;
for(int i = 1; i < c.size(); ++i) {
if(c[i] % base < c[best] % base) {
best = i;
}
}
int papa_label = c[best];
int papa_st = papa_label % base;
int papa_en = papa_label / base;
if(papa_st < s_st) { // there's a papa
for(auto e : c) {
if(e != papa_label) {
childs.pb(e);
}
}
} else { // there's no papa
for(auto e : c) {
childs.pb(e);
}
}
if(papa_st < s_st) {
if(t_st > s_en || t_st < s_st) {
return papa_label;
}
}
sort(all(childs), [&](int xx, int yy) {
return xx % base < yy % base;
});
// find the first child whose end time is bigger than or equal to t's start time
for(int i = 0; i < childs.size(); ++i) {
if(childs[i] / base > t_st) return childs[i];
}
assert(false);
}
int find_next_station(int s, int t, std::vector<int> c) {
if(c.size() == 1) return c[0];
vi ac; int as; int at;
map<int, int> lconv;
if(s < *min_element(all(c))) { // lemma: this is true if and only if I am a starting time
sort(all(c));
int next_st = s + 1;
for(int i = 0; i < csz(c) - 1; ++i) {
lconv[base * c[i] + next_st] = c[i];
ac.pb(base * c[i] + next_st);
next_st = c[i] + 1;
}
// maybe if s is the root of the tree this is an issue
if(s == 0) {
lconv[base * c[csz(c)-1] + 1] = c[csz(c)-1];
ac.pb(base * c[csz(c)-1] + 1); // let it be 0 or some shit
} else {
lconv[base * c[csz(c)-1] + 0] = c[csz(c)-1];
ac.pb(base * c[csz(c)-1] + 0); // let it be 0 or some shit
}
at = (base * t + t); // maybe this is an issue?
as = base * next_st + s;
} else { // I claim I am an ending time and all other people are starting times
sort(all(c));
reverse(all(c));
int next_en = s - 1;
for(int i = 0; i < csz(c) - 1; ++i) {
lconv[base * next_en + c[i]] = c[i];
ac.pb(base * next_en + c[i]);
next_en = c[i] - 1;
}
lconv[c[csz(c)-1] + base * 2002] = c[csz(c)-1];
ac.pb(c[csz(c)-1] + base * 2002); // let it be 0 or some shit
at = (base * t + t); // maybe this is an issue?
as = base * s + next_en;
}
return lconv[find_next_station_bad(as, at, ac)];
}
Compilation message
stations.cpp: In function 'int find_next_station_bad(int, int, std::vector<int>)':
stations.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 1; i < c.size(); ++i) {
| ~~^~~~~~~~~~
stations.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0; i < childs.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
stations.cpp:83:6: warning: unused variable 't_en' [-Wunused-variable]
83 | int t_en = t / base;
| ^~~~
stations.cpp:93:6: warning: unused variable 'papa_en' [-Wunused-variable]
93 | int papa_en = papa_label / base;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
428 KB |
Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
320 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
908 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
846 ms |
512 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
752 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
784 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
