Submission #713313

# Submission time Handle Problem Language Result Execution time Memory
713313 2023-03-21T16:46:19 Z Spade1 Race (IOI11_race) C++14
0 / 100
4 ms 8916 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], 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 [i, w] : adj[x]) {
        dfs2(i, x, 0, w);
        dfs2(i, x, 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;
}

Compilation message

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 [i, w] : adj[x]) {
      |               ^
race.cpp:53:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto [j, w] : adj[cen]) {
      |               ^
race.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
   56 | }
      | ^
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -