Submission #43689

#	Time	Username	Problem	Language	Result	Execution time	Memory
43689		evpipis	Race (IOI11_race)	C++11	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

const int len = 2e5+5, inf = 1e9;
vector<ii> adj[len];
map<ll, int> *cnt, *help;
int ans = inf, sz[len], dep[len], p[len], n, k, isbig[len];
ll shift[len];

void fix(int u, int d){
    sz[u] = 1;
    dep[u] = d;
    for (auto v: adj[u])
        if (v.fi != p[u]){
            p[v.fi] = u;
            fix(v.fi, d+1);
            sz[u] += sz[v.fi];
        }
}

void add(int u, int x, int cur, ll dis){
    if (x == 0 && (*help).count(k-dis-shift[cur]))
        ans = min(ans, dep[u]+(*help)[k-dis-shift[cur]]-2*dep[cur]);
    else{
        if ((*help).count(dis-shift[cur]))
            (*help)[dis-shift[cur]] = min((*help)[dis-shift[cur]], dep[u]);
        else
            (*help)[dis-shift[cur]] = dep[u];
    }

    for (auto v: adj[u])
        if (v.fi != p[u] && !isbig[v.fi])
            add(v.fi, x, cur, dis+v.se);
}

void dfs(int u, int keep){
    int mx = -1;
    ii big = mp(-1, -1);
    for (auto v: adj[u])
        if (v.fi != p[u] && sz[v.fi] > mx){
            mx = sz[v.fi];
            big = v;
        }

    //printf("u = %d, keep = %d, big = %d\n", u, keep, big.fi);

    for (auto v: adj[u])
        if (v.fi != p[u] && v != big)
            dfs(v.fi, 0);
    if (big.fi != -1)
        dfs(big.fi, 1), isbig[big.fi] = 1, shift[u] = shift[big.fi]+big.se, help = cnt;
    else
        help = new map<ll, int>();

    if ((*help).count(k-shift[u]) > 0)
        ans = min(ans, (*help)[k-shift[u]]-dep[u]);
    //printf("one way ans = %d\n", ans);
    if ((*help).count(-shift[u]))
        (*help)[-shift[u]] = min((*help)[-shift[u]], dep[u]);
    else
        (*help)[-shift[u]] = dep[u];
    for (auto v: adj[u])
        if (v.fi != p[u] && v != big)
            add(v.fi, 0, u, v.se), add(v.fi, 1, u, v.se);

    //printf("u = %d, shift = %d, ans = %d\n", u, shift[u], ans);
    //for (map<ll, int>::iterator it = (*help).begin(); it != (*help).end(); it++)
      //  printf("%lld %d\n", it->first+shift[u], it->se);

    if (big.fi != -1)
        isbig[big.fi] = 0;
    if (keep == 1)
        cnt = help;
}

int best_path(int N, int K, int H, int L){
    n = N, k = K;
    for (int i = 0; i < n-1; i++){
        int a = H[i][0], b = H[i][1], c = L[i];
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    fix(0, 0);
    dfs(0, 1);

    if (ans == inf) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int, int)':
race.cpp:86:20: error: invalid types 'int[int]' for array subscript
         int a = H[i][0], b = H[i][1], c = L[i];
                    ^
race.cpp:87:22: error: 'b' was not declared in this scope
         adj[a].pb(mp(b, c));
                      ^
race.cpp:87:25: error: 'c' was not declared in this scope
         adj[a].pb(mp(b, c));
                         ^