#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int MAXN = 1e3+10;
const int MAX = 1e3;
int n, k;
vector <int> adj[MAXN], dw[MAXN];
vector <int> lab;
int chi[MAXN], val[MAXN], cnt;
void dfs(int nw, int par){ // build val, tergantung dfs
val[nw] = cnt++;
for(auto nx : adj[nw]){
if(nx == par) continue;
dw[nw].pb(nx);
dfs(nx, nw);
}
}
void bd(int nw, int par){
chi[nw] = val[nw];
for(auto nx : dw[nw]){
if(nx == par) continue;
bd(nx, nw);
chi[nw] = max(chi[nw], chi[nx]);
}
}
vector<int> label(int N, int K, vector<int> u, vector<int> v) {
n = N; k = K;
lab.clear(); lab.resize(n); cnt = 0;
for(int i=0; i<=n; i++){
adj[i].clear(); dw[i].clear();
chi[i] = 0; val[i] = 0;
}
for(int i=0; i<n-1; i++){
adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
}
dfs(0, -1); bd(0, -1);
for(int i=0; i<n; i++){
lab[i] = val[i] + chi[i]*MAX;
}
//for(int i=0; i<n; i++) cout << i << ' ' << val[i] << ' ' << chi[i] << ' '<< lab[i] << " p\n";
return lab;
}
int find_next_station(int s, int t, vector<int> c) { // c sorted
int num = c.size();
vector <pii> val(num);
for(int i=0; i<num; i++){
val[i].fi = c[i]%MAX; val[i].se = c[i] / MAX;
// idx, max idx di subtree
}
sort(val.begin(), val.end()); // based on idx
//for(auto in : val) cout << in.fi << ' '<< in.se << " xx\n";
int valt = t%MAX, idx = -1;
if(s%MAX==0){ // s itu root
for(int i=0; i<val.size(); i++){
if(val[i].fi <= valt){
idx = i;
}
}
return (val[idx].fi + val[idx].se*MAX);
}
int mx = s/MAX; // kalo nx==0, brati gk ada nx
for(int i=1; i<val.size(); i++){
if(val[i].fi <= valt){
idx = i;
}
}
if(valt < val[1].fi || valt > mx) idx = 0; // parent
return (val[idx].fi + val[idx].se*MAX);
}
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0; i<val.size(); i++){
| ~^~~~~~~~~~~
stations.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=1; i<val.size(); i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
648 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=9000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
824 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=995000 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
291 ms |
1008 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
526 ms |
684 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
282 ms |
1252 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |