Submission #346024

#	Time	Username	Problem	Language	Result	Execution time	Memory
346024		nextgenxing	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

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

typedef pair<int, int> pii;
#define f first
#define s second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
const int MAX_N = 200001;
const int MAX_K = 1000001;
const int INF = 0x3f3f3f3f;

int n, k, ans = INF;
int sz[MAX_N], depth[MAX_N], dist[MAX_N], mins[MAX_K];
bitset<MAX_N> removed;
bitset<MAX_K> done;
vector<pii> tree[MAX_N];
queue<pii> q;

int dfs(int curr, int par = -1){
    sz[curr] = 1;
    for(pii child : tree[curr]){
        if(child.f == par || removed[child.f]) continue;
        sz[curr]+=dfs(child.f, curr);
    }
    return sz[curr];
}

int main(int argc, const char * argv[]){
    cin >> n >> k;
    F0R(i, n-1){
        int a, b, c; cin >> a >> b >> c;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }
    queue<int> q2; q2.push(0);
    while(!q2.empty()){
        int cr = q2.front(); q2.pop();
        int ms = dfs(cr), C; q.push({cr, -1});
        while(!q.empty()){
            bool flag = false;
            int curr = q.front().f, par = q.front().s; q.pop();
            for(pii child : tree[curr]){
                if(child.f == par || removed[child.f]) continue;
                if(sz[child.f]*2 > ms){
                    flag = true;
                    q.push({child.f, curr});
                    break;
                }
            }
            if(!flag){
                C = curr;
                while(q.size()) q.pop();
            }
        }
        depth[C] = 0, dist[C] = 0, q.push({C, -1});
        while(!q.empty()){
            int curr = q.front().f, par = q.front().s; q.pop();
            for(pii child : tree[curr]){
                if(child.f == par || removed[child.f]) continue;
                depth[child.f] = depth[curr]+1;
                dist[child.f] = dist[curr]+child.s;
                q.push({child.f, curr});
            }
        }
        done.reset();
        mins[0] = 0; done[0] = 1;
        for(pii x : tree[C]){
            q.push({x.f, C});
            while(!q.empty()){
                int curr = q.front().f, par = q.front().s; q.pop();
                if(dist[curr] > k) continue;
                if(done[k-dist[curr]]) ans = min(ans, mins[k-dist[curr]]+depth[curr]);
                for(pii child : tree[curr]){
                    if(child.f == par || removed[child.f]) continue;
                    q.push({child.f, curr});
                }
            } q.push({x.f, C});
            while(!q.empty()){
                int curr = q.front().f, par = q.front().s; q.pop();
                if(dist[curr] > k) continue;
                if(!done[dist[curr]]) mins[dist[curr]] = depth[curr];
                else mins[dist[curr]] = min(mins[dist[curr]], depth[curr]);
                done[dist[curr]] = 1;
                for(pii child : tree[curr]){
                    if(child.f == par || removed[child.f]) continue;
                    q.push({child.f, curr});
                }
            }
        }
        removed[C] = 1;
        for(pii x : tree[C])
            if(!removed[x.f])
                q2.push(x.f);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main(int, const char**)':
race.cpp:39:27: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |         int ms = dfs(cr), C; q.push({cr, -1});
      |                           ^
/tmp/ccyzTItq.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccWO1de2.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccWO1de2.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status