# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
713330 |
2023-03-21T17:12:41 Z |
Spade1 |
Race (IOI11_race) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
#define pii pair<int, int>
#define pb push_back
#define st first
#define nd second
using namespace std;
const int maxN = 2e5 + 10;
const int maxL = 1e6 + 10;
vector<pii> adj[maxN];
int sz[maxN], mn = INT_MAX, k;
vector<int> path(maxL, INT_MAX), tmp(maxL, INT_MAX);
bool mark[maxN];
int dfs(int i, int prt=0) {
sz[i] = 1;
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
sz[i] += dfs(j, i);
}
return sz[i];
}
int find_centroid(int i, int n, int prt=0) {
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
if (sz[j] > n/2) return find_centroid(j, n, i);
}
return i;
}
void dfs2(int i, int prt, bool filling, int dis, int cnt=1) {
if (dis > k) return;
if (filling) path[dis] = min(path[dis], cnt);
else if (path[k-dis] != INT_MAX) mn = min(mn, cnt+path[k-dis]);
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
dfs2(j, i, filling, dis+w, cnt+1);
}
}
void decom(int x=0) {
int cen = find_centroid(x, dfs(x));
mark[cen] = 1;
for (auto [j, w] : adj[cen]) {
if (mark[j]) continue;
dfs2(j, cen, 0, w);
dfs2(j, cen, 1, w);
}
path = tmp;
for (auto [j, w] : adj[cen]) {
if (!mark[j]) decom(j);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < N-1; ++i) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
tmp[0] = 0;
path = tmp
decom();
return (mn == INT_MAX ? -1 : mn);
}
Compilation message
race.cpp: In function 'int dfs(int, int)':
race.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
20 | for (auto [j, w] : adj[i]) {
| ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:28:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for (auto [j, w] : adj[i]) {
| ^
race.cpp: In function 'void dfs2(int, int, bool, int, int)':
race.cpp:39:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | for (auto [j, w] : adj[i]) {
| ^
race.cpp: In function 'void decom(int)':
race.cpp:49:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for (auto [j, w] : adj[cen]) {
| ^
race.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for (auto [j, w] : adj[cen]) {
| ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:67:15: error: expected ';' before 'decom'
67 | path = tmp
| ^
| ;
68 | decom();
| ~~~~~