Submission #713329

#	Time	Username	Problem	Language	Result	Execution time	Memory
713329		Spade1	Race (IOI11_race)	C++14	21 / 100	3034 ms	15628 KiB

race

#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, path[maxL];
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);
    }
    for (int i = 1; i < maxL; ++i) path[i] = INT_MAX;
    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]});
    }
    for (int i = 1; i < maxL; ++i) path[i] = INT_MAX;
    path[0] = 0;
    decom();
    return (mn == INT_MAX ? -1 : mn);
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int)':
race.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [j, w] : adj[i]) {
      |               ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for (auto [j, w] : adj[i]) {
      |               ^
race.cpp: In function 'void dfs2(int, int, bool, int, int)':
race.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [j, w] : adj[i]) {
      |               ^
race.cpp: In function 'void decom(int)':
race.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for (auto [j, w] : adj[cen]) {
      |               ^
race.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for (auto [j, w] : adj[cen]) {
      |               ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57