oj.uz

Submission #346034

# Submission time Handle Problem Language Result Execution time Memory
346034 2021-01-09T04:06:39 Z nextgenxing Race (IOI11_race) C++14
0 / 100
 4 ms 5228 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Incorrect 4 ms 5228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Incorrect 4 ms 5228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Incorrect 4 ms 5228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Incorrect 4 ms 5228 KB Output isn't correct
8 Halted 0 ms 0 KB -