Submission #1093351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093351		Aviansh	Race (IOI11_race)	C++17	21 / 100	3010 ms	9040 KiB

race

#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 = 2e9;
    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);
    int ans = 2e9;
    for(int i = 0;i<n;i++){
        map<int,int>mp;
        findLens(i,g,rem,-1,mp,0,0);
        if(mp[k]){
            ans=min(ans,mp[k]);
        }
    }
    if(ans==2e9){
        return -1;
    }
    else{
        return ans;
    }
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:86:9: warning: unused variable 'sz' [-Wunused-variable]
   86 |     int sz[n];
      |         ^~

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