| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1179349 | ema_nicole | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int NMAX = 200002;
using ll = long long;
const int INF = 21e8;
struct muchii {
int nod, dist;
};
vector <vector <muchii>> v;
int n, k;
int parent[NMAX];
int weight[NMAX]; ///ce weight are subarb resp
void dfssize(int start) {
weight[start] = 0;
for(auto x : v[start]) {
if(x.nod == parent[start])
continue;
parent[x.nod] = start;
dfssize(x.nod);
weight[start] += weight[x.nod];
}
weight[start]++;
}
int centroid = -1;
void dfscentroid(int start, int sizee) { ///sizeul e de sus
bool ok = 0;
if(sizee > n / 2)
ok = 1;
for(auto x : v[start]) {
if(x.nod == parent[start])
continue;
if(weight[x.nod] > n / 2)
ok = 1;
}
if(!ok) { ///am gasit centroidul
centroid = start;
return;
}
for(auto x : v[start]) {
if(x.nod == parent[start])
continue;
dfscentroid(x.nod, sizee + weight[start] - weight[x.nod]);
}
}
map <ll, int> umap[NMAX];
int ans = INF; ///dist minima pt suma k
void updateans(int start) {
map <ll, int> lg;
lg.clear();
if(umap[start].find(k) != umap[start].end()) ///dc deja e lant pana in el
ans = min(ans, umap[start][k]);
for(auto x : v[start]) {
if(x.nod == parent[start])
continue;
for(auto var : umap[x.nod]) { ///COMPARAM cu ce avem de la vechii fii
if(lg.find(k - var.first - x.dist) != lg.end()) {
ans = min(ans, lg[k - var.first - x.dist] + var.second + 1);
//if(start == centroid)
//cout << var.first << " "
}
}
for(auto var : umap[x.nod]) { ///UPDATAM
if(lg.find(var.first + x.dist) != lg.end())
lg[var.first + x.dist] = min(lg[var.first + x.dist], var.second + 1);
else
lg[var.first + x.dist] = var.second + 1;
}
}
}
void dfsans(int start) {
bool ok = 0;
for(auto x : v[start]) {
if(x.nod == parent[start])
continue;
dfsans(x.nod);
ok = 1;
for(auto var : umap[x.nod]) { ///updatam distantele din x.nod
///first = distanta, second = cate muchii
if(umap[start].find(var.first + x.dist) != umap[start].end())
umap[start][var.first + x.dist] = min(umap[start][var.first + x.dist], var.second + 1);
else
umap[start][var.first + x.dist] = var.second + 1;
}
umap[start][x.dist] = 1;
}
if(!ok) ///frunza
umap[start][0] = 0;
else ///cautam dc exista drumuri de suma k
updateans(start);
/*cout << "NODUL " << start << '\n';
for(auto var : umap[start])
cout << var.first << " " << var.second << '\n';*/
}
int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
n = N, k = K;
v.resize(n + 1);
for(int i = 0; i < n - 1; i++) {
v[h[i][0]].push_back({h[i][1], l[i]});
v[h[i][1]].push_back({h[i][0], l[i]});
}
/*for(int i = 0; i < n; i++) {
cout << "nodul " << i << '\n';
for(auto x : v[i])
cout << x.nod << " ";
cout << '\n';
}*/
parent[0] = -1;
dfssize(0);
/*for(int i = 0; i < n; i++)
cout << weight[i] << " ";
cout << '\n';*/
dfscentroid(0, 0);
parent[centroid] = -1;
dfssize(centroid); ///reindexam parintii
/*for(int i = 0; i < n; i++)
cout << parent[i] << " ";
cout << '\n';*/
dfsans(centroid);
for(int i = 48; i < 51; i += 2) {
cout << "NODUL " << i << '\n';
for(auto var : umap[i])
cout << var.first + (i - 1) % 2 << " " << var.second << '\n';
//if(umap[i].find(k) != umap[i].end())
//cout << "NODUL " << i << " " << umap[i][k] << '\n';
}
if(ans == INF)
ans = -1;
return ans;
}
int h[NMAX][2];
int l[NMAX];
int main()
{
int N, K;
cin >> N >> K;
for(int i = 0; i < N - 1; i++)
cin >> h[i][0] >> h[i][1] >> l[i];
cout << best_path(N, K, h, l);
return 0;
}
/*
100 100
0 1 3
1 2 6
2 3 1
3 4 9
4 5 8
5 6 0
6 7 6
7 8 10
8 9 4
9 10 5
10 11 1
11 12 1
12 13 9
13 14 4
14 15 5
15 16 7
16 17 7
17 18 5
18 19 6
19 20 8
20 21 1
21 22 5
22 23 1
23 24 2
24 25 3
25 26 7
26 27 8
27 28 3
28 29 9
29 30 9
30 31 3
31 32 1
32 33 8
33 34 5
34 35 6
35 36 5
36 37 5
37 38 2
38 39 8
39 40 1
40 41 3
41 42 0
42 43 2
43 44 8
44 45 3
45 46 8
46 47 5
47 48 3
48 49 0
49 50 1
50 51 0
51 52 3
52 53 3
53 54 3
54 55 7
55 56 6
56 57 2
57 58 1
58 59 3
59 60 5
60 61 2
61 62 2
62 63 9
63 64 3
64 65 3
65 66 0
66 67 1
67 68 8
68 69 9
69 70 1
70 71 0
71 72 7
72 73 5
73 74 7
74 75 7
75 76 3
76 77 6
77 78 5
78 79 6
79 80 2
80 81 2
81 82 7
82 83 4
83 84 2
84 85 0
85 86 4
86 87 0
87 88 7
88 89 8
89 90 5
90 91 8
91 92 9
92 93 0
93 94 5
94 95 8
95 96 8
96 97 3
97 98 9
98 99 0
12
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3
4
5
4
6
3
2
5
6
7
*/