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 <bits/stdc++.h>
#include "stations.h"
using namespace std;
const int N = 1000;
int sz[N], pref[N];
vector<int> val, g[N];
void pre_dfs(int v, int p = -1){
sz[v] = 1;
for (int u : g[v]){
if (u == p) continue;
pre_dfs(u, v);
sz[v] += sz[u];
}
}
void dfs(int v, int p = -1){
pref[v] = 0;
for (int u : g[v]){
if (u == p) continue;
pref[v] += sz[u];
val[u] = val[v] - sz[v] + pref[v];
dfs(u, v);
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
for (int i = 0; i < n; i ++)
pref[i] = sz[i] = 0, g[i].clear();
val.resize(n, 0);
for (int i = 0; i < n - 1; i ++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
pre_dfs(0);
val[0] = sz[0];
dfs(0);
for (int i = 0; i < n; i ++)
val[i]--;
return val;
}
int find_next_station(int s, int t, vector<int> c){
if (t > s) return c.back();
if (t == s) return s;
for (int x : c){
if (t <= x){
return x;
}
}
return c.back();
}
/*int main(){
int t;
cin >> t;
while (t--){
int n, k;
cin >> n >> k;
vector<int> u(n - 1), v(n - 1);
for (int i = 0; i < n - 1; i ++)
cin >> u[i] >> v[i];
label(n, k, u, v);
for (int i = 0; i < n; i ++){
cout << i << " :: " << val[i] << endl;
}
// for (int i = 0; i < n; i ++){
// for (int j = 0; j < n; j ++){
// if (i == j) continue;
// vector<int> adj;
// for (int x : g[i])
// adj.push_back(val[x]);
// sort(adj.begin(), adj.end());
// int res = find_next_station(val[i], val[j], adj);
// cout << val[i] << " -- " << val[j] << " == " << res << endl;
// }
// }
}
}*/
/*
1
23 23
1 0
1 2
1 3
0 4
0 5
0 6
2 7
3 8
3 9
4 10
4 11
5 12
6 13
7 14
7 15
8 16
9 17
9 18
9 19
14 20
14 21
14 22
*/
# | 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... |