제출 #723118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723118		sochu	경주 (Race) (IOI11_race)	C++17	0 / 100	7 ms	9704 KiB

race

  #include <bits/stdc++.h>
 #define pii pair < int , int > 

using namespace std;
	const int N = 2e5 + 10;
 
    set < pii > G[N];
    int sz[N];
    int a[N * 10];
 
    int K;
 
    void getsize(int node , int par)
    {
        sz[node] = 1;
 
        for(auto to : G[node])
            if(to.first != par)
            {
                getsize(to.first , node);
                sz[node] += sz[to.first];
            }
    }
 
    int find(int node , int par , int n)
    {
        for(auto to : G[node])
            if(to.first != par)
            {
                if(sz[to.first] > n / 2)
                    return find(to.first , node , n);
            }
 
        return node;
    }
 
    int ans = INT_MAX;
 
    void get(int node , int par , int len , int h)
    {
        if(len <= K && a[K - len])
            ans = min(ans , a[K - len] + h - 1);
 
        for(auto to : G[node])
            if(to.first != par)
                get(to.first , node , len + to.second , h + 1);
    }
 
    void add(int node , int par , int len , int h)
    {
        if(len <= K)
        {
            if(a[len] == 0) a[len] = h - 1;
            else a[len] = min(a[len] , h - 1);
        }
 
        for(auto to : G[node])
            if(to.first != par)
                add(to.first , node , len + to.second , h + 1);
    }
 
    void solve(int root)
    {
        for(int i = 0 ; i <= K ; i++)
            a[i] = 0;
 
        for(auto to : G[root])
        {
            get(to.first , root , to.second , 2);
            add(to.first , root , to.second , 2);
        }
    }
 
    void decomp(int root)
    {
        getsize(root , 0);
        int c = find(root , 0 , sz[root]);
        solve(c);
 
        for(auto to : G[c])
        {
            G[to.first].erase({c , to.second});
            decomp(to.first);
        }
    }
 
 
    int best_path(int n , int k , int H[][2] , int L[])
    {
        K = k;
 
        for(int i = 0 ; i < n - 1 ; i++)
        {
            int x = H[i][0];
            int y = H[i][1];
 
            G[x].insert({y , L[i]});
            G[y].insert({x , L[i]});
        }
 
        decomp(1);
        if(ans == INT_MAX) ans = -1;
        return ans;
    }

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