Submission #713330

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713330	2023-03-21T17:12:41 Z	Spade1	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

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;
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();
      |     ~~~~~