Submission #349649

#	Time	Username	Problem	Language	Result	Execution time	Memory
349649		nextgenxing	Race (IOI11_race)	C++14	0 / 100	4 ms	5248 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
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 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 best_path(int n, int k, int H[][2], int L[]){
    F0R(i, n-1){
        tree[H[i][0]].push_back({H[i][1], L[i]});
        tree[H[i][1]].push_back({H[i][0], L[i]});
    }
    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) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:38:27: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         int ms = dfs(cr), C; q.push({cr, -1});
      |                           ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57