Submission #1090020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090020		Ice_man	Race (IOI11_race)	C++17	100 / 100	367 ms	76276 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#include <vector>
 
#define maxn 2000005
#define mod 1000000007
#define INF 1000000005
 
#define X first
#define Y second
 
using namespace std;
 
vector <pair <int, int>> v[maxn];
int sz[maxn];
 
int used[maxn];
 
 
int find_sz(int node, int parent)
{
    sz[node] = 1;
 
    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;
 
        sz[node] += find_sz(e.X , node);
    }
 
    return sz[node];
}
 
 
 
int find_centroid(int node, int parent, int _sz)
{
    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;
 
        if(sz[e.X] * 2 > _sz)
            return find_centroid(e.X, node, _sz);
 
    }
 
    return node;
}
 
int c = 1e8;
int ans = INF;
 
int help[maxn];
 
void dfs1(int node, int parent, int depth, int weight, int k)
{
    if(weight > 0 && weight <= k)
        help[weight] = 1e8;
 
    if(k > weight)
        help[k - weight] = 1e8;
 
    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;
 
        dfs1(e.X, node, depth + 1, weight + e.Y, k);
    }
 
}
 
void dfs2(int node, int parent, int depth, int weight, int k)
{
    if(weight <= k && parent != -1)
        ans = min(ans, help[k - weight] + depth);
 
    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;
 
        dfs2(e.X, node, depth + 1, weight + e.Y, k);
    }
 
}
 
 
void dfs3(int node, int parent, int depth, int weight, int k)
{
    if (k >= weight && parent != -1)
        help[weight] = min(help[weight], depth);
 
    for (pair <int, int> e : v[node])
    {
        if (e.X == parent || used[e.X])
            continue;
 
        dfs3(e.X, node, depth + 1, weight + e.Y , k);
    }
}
 
 
 
 
void decompose(int node , int k)
{
    int cur_sz = find_sz(node , -1);
 
    int centroid = find_centroid(node , -1 , cur_sz);
 
    used[centroid] = true;
 
    for(pair <int , int> e : v[centroid])
    {
        if(used[e.X] == true)
            continue;
 
        dfs1(e.X , centroid , 1 , e.Y , k);
    }
 
    for(pair <int , int> e : v[centroid])
    {
        if(used[e.X] == true)
            continue;
 
        dfs2(e.X, centroid , 1 , e.Y , k);
        dfs3(e.X , centroid , 1 , e.Y , k);
 
    }
 
    for(pair <int , int> e : v[centroid])
    {
        if(used[e.X] == true)
            continue;
 
        decompose(e.X , k);
    }
}
 
 
 
int best_path(int n , int k , int h[][2] , int l[])
{
    for(int i = 0; i < n - 1; i++)
    {
        v[h[i][0]].push_back({h[i][1] , l[i]});
        v[h[i][1]].push_back({h[i][0] , l[i]});
    }
 
    help[0] = 0;
    decompose(0 , k);
 
    if(ans > n)
        return -1;
 
    return ans;
 
}
 

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