Submission #43687

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
43687	2018-03-19T15:35:08 Z	evpipis	Race (IOI11_race)	C++11	Compilation error	0 ms	0 KB

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 main(){
    scanf("%d %d", &n, &k);
    //printf("n = %d, k = %d\n", n, k);
    for (int i = 0; i < n-1; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        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

race.cpp: In function 'int main()':
race.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccSf5OSc.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccEAht9u.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccEAht9u.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status