Submission #426057

#	Time	Username	Problem	Language	Result	Execution time	Memory
426057		someone	Race (IOI11_race)	C++14	100 / 100	942 ms	59328 KiB

race

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

const int N = 2e5 + 10, K = 1e6 + 10, INF = 1e9;

bool ch[K];
vector<int> adj[N], len[N], upd;
int h[N], longueur, mini = INF, minAut[K];

void getMin(int i, int pre, int dist, int nbAut) {
    if(h[i] != -1 || dist > longueur)
        return;
    mini = min(mini, nbAut + minAut[longueur - dist]);
    nbAut++;
    int t = adj[i].size();
    for(int j = 0; j < t; j++)
        if(adj[i][j] != pre)
            getMin(adj[i][j], i, dist + len[i][j], nbAut);
}

void update(int i, int pre, int dist, int nbAut) {
    if(h[i] != -1 || dist > longueur)
        return;
    if(!ch[dist]) {
        ch[dist] = true;
        upd.push_back(dist);
    }
    minAut[dist] = min(minAut[dist], nbAut);
    nbAut++;
    int t = adj[i].size();
    for(int j = 0; j < t; j++)
        if(adj[i][j] != pre)
            update(adj[i][j], i, dist + len[i][j], nbAut);
}

int centroid(int i, int pre, int sz, int id) {
    if(h[i] != -1)
        return 0;
    //cout << "CALL " << i << ' ' << sz << ' ' << id << '\n';
    int t = adj[i].size(), s[t], sum = 1, v = -1;
    for(int j = 0; j < t; j++)
        if(adj[i][j] == pre) {
            v = j;
        } else {
            s[j] = centroid(adj[i][j], i, sz, id);
            sum += s[j];
        }
    if(v != -1)
        s[v] = sz - sum;
    int maxi = 0;
    for(int j = 0; j < t; j++)
        maxi = max(maxi, s[j]);
    //cout << "TEST " << i << ' ' << h[i] << ' ' << maxi << ' ' << (sz+1)/2 << ' ' << sz << '\n';
    if(h[i] == -1 && maxi <= sz/2) {
        h[i] = id;
        minAut[0] = 0;
        upd.push_back(0);
        for(int j = 0; j < t; j++) {
            getMin(adj[i][j], i, len[i][j], 1);
            update(adj[i][j], i, len[i][j], 1);
        }
        for(int j : upd) {
            ch[j] = false;
            minAut[j] = INF;
        }
        upd.clear();
        //cout << i << ' ' << h[i] << ' ' << t << '\n';
        id++;
        /*for(int j = 0; j < t; j++)
            cout << ' ' << adj[i][j] << ' ' << s[j] << '\n';*/
        for(int j = 0; j < t; j++)
            centroid(adj[i][j], i, s[j], id);
    }
    return sum;
}

int best_path(int n, int k, int H[][2], int L[]) {
    longueur = k;
    for(int i = 0; i < K; i++)
        minAut[i] = INF;
    for(int i = 0; i < n; i++)
        h[i] = -1;
    for(int i = 0; i < n-1; i++) {
        len[H[i][0]].push_back(L[i]);
        len[H[i][1]].push_back(L[i]);
        adj[H[i][0]].push_back(H[i][1]);
        adj[H[i][1]].push_back(H[i][0]);
    }
    centroid(0, -1, n, 0);
    if(mini == INF)
        return -1;
    return mini;
}

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