oj.uz

Submission #1093327

# Submission time Handle Problem Language Result Execution time Memory
1093327 2024-09-26T14:59:44 Z Aviansh Race (IOI11_race) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
#include "race.h"

using namespace std;

int subSize(int st, vector<pair<int,int>>(&g)[], int sz[], int par, bool rem[]){
    sz[st]=1;
    for(pair<int,int> p : g[st]){
        int c = p.first;
        if(rem[c]||c==par) continue;
        sz[st]+=subSize(c,g,sz,st,rem);
    }
    return sz[st];
}

int findCentroid(int node, vector<pair<int,int>>(&g)[], int siz, bool rem[], int par, int sizes[]){
    for(pair<int,int> p : g[node]){
        int c = p.first;
        if(c==par||rem[c]) continue;
        if(sizes[c]*2>siz){
            return findCentroid(c,g,siz,rem,node,sizes);
        }
    }
    return node;
}

void findLens(int st, vector<pair<int,int>>(&g)[], bool rem[], int par, map<int,int>(&mp), int dep, int len){
    for(pair<int,int> p : g[st]){
        int c = p.first;
        int d = p.second;
        if(c==par||rem[c]) continue;
        if(mp[dep+d]==0){
            mp[dep+d]=len+1;
        }
        else{
            mp[dep+d]=min(mp[dep+d],len+1);
        }
        findLens(c,g,rem,st,mp,dep+d,len+1);
    }
}

int buildDecomp(int node, vector<pair<int,int>>(&g)[], bool rem[], int sz[], int k){
    int centroid = findCentroid(node,g,subSize(node,g,sz,-1,rem),rem,-1,sz);
    int ans = INT_MAX;
    map<int,int>mp;
    rem[centroid]=1;
    for(pair<int,int> p : g[centroid]){
        int c = p.first;
        if(rem[c]) continue;
        map<int,int>temp;
        temp[p.second]=1;
        findLens(c,g,rem,-1,temp,p.second,0);
        for(pair<int,int>pa : temp){
            if(mp[k-pa.first]){
                ans=min(ans,mp[k-pa.first]+pa.second);
            }
        }
        for(pair<int,int>pa:temp){
            if(mp[pa.first]){
                mp[pa.first]=min(mp[pa.first],pa.second);
            }
            else{
                mp[pa.first]=pa.second;
            }
        }
    }
    if(mp[k]){
        ans=min(ans,mp[k]);
    }
    for(pair<int,int>p:g[centroid]){
        int c = p.first;
        if(rem[c])continue;
        ans=min(ans,buildDecomp(c,g,rem,sz,k));
    }
    return ans;
}

int best_path(int n, int k, int e[][2], int w[])
{
    vector<pair<int,int>>g[n];
    for(int i = 0;i<n-1;i++){
        g[e[i][0]].push_back({e[i][1],w[i]});
        g[e[i][1]].push_back({e[i][0],w[i]});
    }
    bool rem[n];
    int sz[n];
    fill(rem,rem+n,0);
    int ans = buildDecomp(0,g,rem,sz,k);
    if(ans==INT_MAX){
        return -1;
    }
    else{
        return ans;
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -