Submission #331435

#	Time	Username	Problem	Language	Result	Execution time	Memory
331435		2fat2code	Race (IOI11_race)	C++17	0 / 100	4 ms	5100 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int nmax = 200005;

int tot;
int sub[nmax], used[nmax], ans = 1e9;
vector <pair<int,int>> nod[nmax];

void calc(int s, int par = 0){
    sub[s] = 1;
    for(auto it : nod[s]){
        if(used[it.fr] == 0 && it.fr != par){
            calc(it.fr, s);
            sub[s] += sub[it.fr];
        }
    }
}

int find_centroid(int s, int nec, int par = 0){
    for(auto it : nod[s]){
        if(used[it.fr] == 0 && it.fr != par && sub[it.fr] > nec){
            return find_centroid(it.fr, nec, s);
        }
    }
    return s;
}

void dfs(int s, map<int,int>&aux, int len = 0, int nredge = 0, int par = 0){
    if(aux.count(len) == 0){
        aux[len] = nredge;
    }
    else{
        aux[len] = min(aux[len], nredge);
    }
    for(auto it : nod[s]){
        if(it.fr != par && used[it.fr] == 0){
            dfs(it.fr, aux, len + it.sc, nredge + 1, s);
        }
    }
}

void centroid(int s){
    calc(s);
    int centr = find_centroid(s, sub[s] / 2);
    map<int, int> aux, fin;
    fin[0] = 0;
    used[centr] = 1;
    for(auto it : nod[centr]){
        if(used[it.fr] == 0){
            dfs(it.fr, aux);
            for(auto it1 : aux){
                if(fin.count(tot - it1.fr) == 1){
                    ans = min(ans, it1.sc + fin[tot - it1.fr]);
                }
            }
            for(auto it1 : aux){
                if(fin.count(it1.fr) == 0){
                    fin[it1.fr] = it1.sc;
                }
                else{
                    fin[it1.fr] = min(fin[it1.fr], it1.sc);
                }
            }
            aux.clear();
            centroid(it.fr);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    tot = K;
    for(int i=1;i<N;i++){
        nod[H[i-1][0]].push_back({H[i-1][1], L[i-1]});
        nod[H[i-1][1]].push_back({H[i-1][0], L[i-1]});
    }
    centroid(0);
    if(ans == 1e9){
        return -1;
    }
    else{
        return ans;
    }
}

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