Submission #405059

#	Time	Username	Problem	Language	Result	Execution time	Memory
405059		Vladth11	Race (IOI11_race)	C++14	21 / 100	3064 ms	41464 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"race.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000009;
const ll BLOCK = 225;
const ll base = 31;
const ll base2 = 53;
const ll nr_of_bits = 21;

vector <pii> v[NMAX];
int best = 2e9;
int k;
int sz[NMAX];
int total;
int viz[NMAX];
int d[NMAX];
vector <pii> mp[1000001];

void getsize(int node, int p){
    sz[node] = 1;
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        sz[node] += sz[x.first];
    }
}

int centroid(int node, int p){
    for(auto x : v[node]){
        if(viz[x.first] || x.first == p){
            continue;
        }
        if(sz[x.first] > total / 2)
            return centroid(x.first, node);
    }
    return node;
}

int OneCentroid(int node){
    getsize(node, 0);
    return centroid(node, 0);
}


void ComputeDist(int node, int p, int subTree, int dist, int level){
    d[node] = dist;
    pii act = {level, subTree};
    if(dist <= k && (!mp[dist].size() || mp[dist].back().first >= level))
        mp[dist].push_back(act);
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        ComputeDist(x.first, node, subTree, d[node] + x.second, level + 1);
    }
}

void Erase(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k && (mp[dist].size() && mp[dist].back() == act))
        mp[dist].pop_back();
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Erase(x.first, node, subTree, level + 1);
    }
}

void Add(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k && (!mp[dist].size() ||mp[dist].back().first >= level))
        mp[dist].push_back(act);
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Add(x.first, node, subTree, level + 1);
    }
}

void Compute(int node, int p, int level){
    int trb = k - d[node];
    if(trb >= 0 && mp[trb].size() != 0)
    {
        int b = mp[trb].back().first;
        best = min(best, b + level);
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Compute(x.first, node, level + 1);
    }
}


void CD(int node){
    int c = OneCentroid(node);
    viz[c] = 1;
    for(int i = 0; i <= k; i++)
        mp[i].clear();
    mp[0].push_back({0, 0});
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        ComputeDist(x.first, c, x.first, x.second, 1);
    }
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        Erase(x.first, c, x.first, 1);
        Compute(x.first, 0, 1);
        Add(x.first, c, x.first, 1);
    }
     for(auto x : v[c]){
        if(viz[x.first])
            continue;
        CD(x.first);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < N - 1; i++){
        int a = H[i][0] + 1;
        int b = H[i][1] + 1;
        v[a].push_back({b, L[i]});
        v[b].push_back({a, L[i]});
    }
    CD(1);
    if(best == 2e9)
        best = -1;
    return best;
}

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