Submission #1142192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142192		AtabayRajabli	Race (IOI11_race)	C++20	0 / 100	3 ms	4932 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 2e5 + 5;
int n, m, k, ans = sz, w[sz], len[sz], used[sz], d[sz];
vector<array<int, 2>> g[sz];
vector<int> cur;
map<int, int> mp;

void dfs(int v, int p)
{
    w[v] = 1;
    for(auto i : g[v])
    {
        if(i[0] == p) continue;
        dfs(i[0], v);
        w[v] += w[i[0]];                   
    }
}
    
int fnd(int v, int p = -1)
{
    for(auto i : g[v])
    {
        if(i[0] == p || used[i[0]]) continue;
        if(w[i[0]] > w[v] / 2)
        {
            w[v] -= w[i[0]];
            w[i[0]] += w[v];
            return fnd(i[0], v);
        }
    }
    return v;
}

void dist(int v, int p, int cst)
{
    if(d[p] + cst > k) return;
    len[v] = len[p] + 1;
    d[v] = d[p] + cst; 
    cur.push_back(v);
    for(auto i : g[v])
    {
        if(i[0] == p || used[i[0]]) continue;
        dist(i[0], v, i[1]);
    }
}

void build(int v)
{
    int c = fnd(v);
    used[c] = 1;
    d[c] = 0;
    len[c] = 0;
    mp[0] = 0;
    for(auto x : g[c])
    {
        if(used[x[0]]) continue;
        dist(x[0], c, x[1]);
        for(int j : cur)
        {
            if(mp.find(k - d[j]) != mp.end()) 
                ans = min(ans, mp[k - d[j]] + len[j]);
        }
        for(int j : cur)
        {
            if(mp.find(d[j]) == mp.end()) mp[d[j]] = len[j];
            else mp[d[j]] = min(mp[d[j]], len[j]);
        }
    }
    cur.clear();
    mp.clear();
    for(auto x : g[c])
    {
        if(!used[x[0]]) 
            build(x[0]);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    for(int i = 1; i <= n; i++)
    {
        g[i].clear();
        w[i] = 0;
        len[i] = 0;
        d[i] = 0;
        used[i] = 0;
    }
    mp.clear();
    cur.clear();
    ans = sz;

    for(int i = 0; i < n - 1; i++)
    {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(1, 1);
    build(1);
    if(ans >= sz) ans = -1;
    return ans;
}

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