Submission #109677

#	Time	Username	Problem	Language	Result	Execution time	Memory
109677		someone_aa	Race (IOI11_race)	C++17	100 / 100	1138 ms	34948 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
const int maxk = 1100000;

vector<pair<int,int> > g[maxn];
bool deleted[maxn];
int sbtsum[maxn], parent[maxn];
int n, k;

class path {
public:
    int node, sum, cnt;
};

vector<path> curr_paths;
void find_paths(int node, int p, int sum, int cnt) {
    curr_paths.pb({node, sum, cnt});
    for(auto i:g[node]) {
        if(deleted[i.first] || i.first == p) continue;
        find_paths(i.first, node, sum+i.second, cnt+1);
    }
}

int min_cnt[maxk];
int result;

void solve(int node) {
    //memset(min_cnt,0,sizeof(min_cnt));
    for(auto i:g[node]) {
        if(deleted[i.first]) continue;
        curr_paths.clear();
        find_paths(i.first, -1, 0, 0);

        for(auto j:curr_paths) {
            int curr = j.sum + i.second;

            if(curr > k) continue;
            else if(curr == k) result = min(result, j.cnt+1);
            else {
                int diff = k - curr;
                if(min_cnt[diff] != 0) result = min(result, min_cnt[diff] + j.cnt + 1);
            }
        }

        for(auto j:curr_paths) {
            int curr = j.sum + i.second;

            if(curr > k) continue;

            int newval = j.cnt + 1;
            if(min_cnt[curr] == 0) min_cnt[curr] = newval;
            else min_cnt[curr] = min(min_cnt[curr], newval);
        }
    }

    for(auto i:g[node]) {
        if(deleted[i.first]) continue;
        curr_paths.clear();
        find_paths(i.first, -1, 0, 0);

        for(auto j:curr_paths) {
            int curr = j.sum + i.second;

            if(curr > k) continue;
            min_cnt[curr] = 0;
        }
    }
}

void dfs0(int node, int p) {
    sbtsum[node] = 1;
    parent[node] = p;
    for(auto i:g[node]) {
        if(deleted[i.first] || i.first == p) continue;
        dfs0(i.first, node);
        sbtsum[node] += sbtsum[i.first];
    }
}

void decompose(int node) {
    dfs0(node, -1);

    int best_size = sbtsum[node];
    int centroid = node;

    queue<int>q;
    q.push(node);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();

        int curr_size = sbtsum[node] - sbtsum[curr];
        for(auto i:g[curr]) {
            if(deleted[i.first] || parent[i.first] != curr) continue;
            curr_size = max(curr_size, sbtsum[i.first]);
            q.push(i.first);
        }

        if(curr_size < best_size) {
            best_size = curr_size;
            centroid = curr;
        }
    }

    deleted[centroid] = true;
    solve(centroid);
    for(auto i:g[centroid]) {
        if(deleted[i.first]) continue;
        decompose(i.first);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    result = INT_MAX;
    for(int i=0;i<N-1;i++) {
        int a = H[i][0];
        int b = H[i][1];
        int c = L[i];

        g[a].pb(mp(b, c));
        g[b].pb(mp(a, c));
    }

    decompose(0);
    if(result == INT_MAX) return -1;
    return result;
}

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