oj.uz

Submission #1005809

# Submission time Handle Problem Language Result Execution time Memory
1005809 2024-06-23T05:38:58 Z Mardonbekhazratov Race (IOI11_race) C++17
0 / 100
 1 ms 2396 KB 
#include<race.h>
#include<bits/stdc++.h>

using namespace std;

vector<int>subtree;
vector<bool>removed;
vector<vector<pair<int,int>>>v;

int get_size(int node,int parent = -1){
    subtree[node]=1;
    for(auto [x,w]:v[node]){
        if(!removed[x] && x!=parent){
            subtree[node]+=get_size(x,node);
        }
    }
    return subtree[node];
}

int get_centroid(int node, int n, int parent = -1){
    for(auto [x,w]:v[node]){
        if(!removed[x] && x!=parent && subtree[x]*2>n)
            return get_centroid(x,n,node);
    }
    return node;
}

int n,k;
int ans = 1e9;

void get_cnt(int node, map<int,int> &cnt, int dis, bool filling, int depth = 1, int parent = -1){
    if(dis>k) return;

    if(filling) cnt[dis]=(cnt[dis]==0?depth:min(depth,cnt[dis]));
    else ans = min(ans,(cnt[k-dis]==0?(int)1e9:cnt[k-dis])+depth);
    for(auto [x,w]:v[node]){
        if(x!=parent && !removed[x]){
            get_cnt(x,cnt,dis+w,filling,depth+1,node);
        }
    }
}

void build_centroid(int node = 0){
    int centroid = get_centroid(node,get_size(node));

    removed[centroid]=true;

    map<int,int>cnt;
    for(auto [x,w]:v[centroid]){
        if(!removed[x]){
            get_cnt(x,cnt,w,false);
            get_cnt(x,cnt,w,true);
        }
    }

    for(auto [x,w]:v[centroid]){
        if(!removed[x]){
            build_centroid(x);
        }
    }
}


int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    subtree.resize(n);
    v.resize(n);
    removed.assign(n,false);
    for(int i=0;i<n-1;i++){
        v[H[i][0]].push_back({H[i][1],L[i]});
        v[H[i][1]].push_back({H[i][0],L[i]});
    }
    build_centroid();

    return ans == (int)1e9 ? -1 : ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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