Submission #1142174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142174		nasir_bashirov	경주 (Race) (IOI11_race)	C++17	31 / 100	235 ms	49884 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int sz = 1e6 + 5;
int n, k, res = 1e9, dp[sz], best[sz];
bool used[sz];
vii g[sz];
vii v, vv;

void dfs(int node, int par){
    dp[node] = 1;
    for(pii i : g[node]){
        if(i.first == par or used[i.first]) continue;
        dfs(i.first, node);
        dp[node] += dp[i.first];
    }
}

int find_centroid(int node, int par, int tsz){
    for(pii i : g[node]){
        if(i.first == par or used[i.first]) continue;
        if(dp[i.first] > tsz / 2)   return find_centroid(i.first, node, tsz);
    }
    return node;
}

void calc(int node, int par, int dis, int h){
    if(dis > k) return;
    v.push_back({dis, h});
    for(pii i : g[node]){
        if(i.first == par or used[i.first]) continue;
        calc(i.first, node, dis + i.second, h + 1);
    }
}

void build(int node){
    dfs(node, node);
    int centroid = find_centroid(node, node, dp[node]);
    for(pii i : g[centroid]){
        if(used[i.first]) continue;
        v.clear();
        calc(i.first, centroid, i.second, 1);
        for(pii j : v){
            // cout << node << " " << i.first << " " << i.second << " : " << best[k - j.first] << " " << j.first << " " << j.second << endl;
            res = min(res, best[k - j.first] + j.second);
            vv.push_back(j);
        }
        for(pii j : v){
            best[j.first] = min(best[j.first], j.second);
        }
    }
    for(pii i : vv){
        best[i.first] = 1e9;
    }
    vv.clear();
    used[centroid] = true;
    for(pii i : g[centroid]){
        if(used[i.first])   continue;
        build(i.first);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0; i < n; i++){
        if(H[i][0] == H[i][1])  continue;
        g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
        g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
        // cout << "edge : " << H[i][0] << " " << H[i][1] << endl;
    }
    for(int i = 1; i <= n; i++) best[i] = 1e9;
    best[0] = 0;
    build(1);
    if(res == 1e9)  res = -1;
    return res;
}

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