Submission #348311

#	Time	Username	Problem	Language	Result	Execution time	Memory
348311		nicolaalexandra	Race (IOI11_race)	C++14	100 / 100	2281 ms	54164 KiB

race

#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
#include "race.h"
using namespace std;

int n,k,ans;
vector <pair<int,int> > L[DIM];

int viz[DIM],s[DIM],mrk[DIM],dp[DIM],level[DIM];
map <int,int> mp,mp2;

void dfs (int nod, int tata, int &cnt){
    s[nod] = 1;
    cnt++;
    for (auto it : L[nod]){
        int vecin = it.first;
        if (vecin != tata && !mrk[vecin]){
            dfs (vecin,nod,cnt);
            s[nod] += s[vecin];
        }}}

int get_centroid (int nod, int tata, int n){
    //viz[nod] = 1;
    int maxim = 0, heavy_son = 0;
    for (auto it : L[nod]){
        int vecin = it.first;
        if (mrk[vecin] || vecin == tata)
            continue;
        if (s[vecin] > maxim)
            maxim = s[vecin], heavy_son = vecin;
    }

    if (maxim <= n/2 && n - s[nod] <= n/2)
        return nod;
    else return get_centroid(heavy_son,nod,n);
}

int solve (int nod){

    //memset (viz,0,sizeof viz);
    //memset (s,0,sizeof s);

    int n = 0;
    dfs (nod,0,n);

   // memset (viz,0,sizeof viz);
    int sol = get_centroid (nod,0,n);

    mrk[sol] = 1;
    return sol;
}

void dfs2 (int nod, int tata, int cost, int level){

    //dp[nod] = dp[tata] + cost;
    //level[nod] = 1 + level[tata];

    if (!mp2[cost])
        mp2[cost] = level;
    else mp2[cost] = min (mp2[cost],level);

    for (auto it : L[nod]){
        int vecin = it.first;
        if (!mrk[vecin] && vecin != tata)
            dfs2 (vecin,nod,cost + it.second,level+1);

    }

}

void decompose (int nod){

    int centroid = solve (nod);

    mp.clear();
    for (auto it : L[centroid]){
        int vecin = it.first;
        if (mrk[vecin])
            continue;

        mp2.clear();

        //dp[centroid] = 0;
        dfs2 (vecin,centroid,it.second,1);

        for (auto it2 : mp2){

            int cost = it2.first;

            if (mp[k-cost])
                ans = min (ans,mp[k-cost] + it2.second);

            if (cost == k)
                ans = min (ans,it2.second);
        }


        for (auto it2 : mp2){
            int cost = it2.first;
            if (!mp[cost])
                mp[cost] = it2.second;
            else mp[cost] = min (mp[cost],it2.second);
        }

    }


    for (auto it : L[centroid]){
        int vecin = it.first;
        if (!mrk[vecin])
            decompose (vecin);
    }

}


int best_path (int N, int K, int h[][2], int l[]){

    n = N, k = K;
    ans = n+1;

    int i,j,x,y;
    for (i=0;i<n-1;i++){
        x = h[i][0]+1, y = h[i][1]+1;
        L[x].push_back(make_pair(y,l[i]));
        L[y].push_back(make_pair(x,l[i]));
    }

    decompose (1);

    if (ans == n+1)
        return -1;
    return ans;

}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:123:11: warning: unused variable 'j' [-Wunused-variable]
  123 |     int i,j,x,y;
      |           ^

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