Submission #713320

#	Time	Username	Problem	Language	Result	Execution time	Memory
713320		Spade1	Race (IOI11_race)	C++14	0 / 100	16 ms	19564 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], mx, 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] != -1) 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);
    }
}

int 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] = -1;
//    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]});
    }
    memset(path, -1, sizeof(path));
    path[0] = 0;
    decom();
    return (mn == INT_MAX ? -1 : mn);
}

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 'int 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:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

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