제출 #1271459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271459		KALARRY	Race (IOI11_race)	C++20	21 / 100	3094 ms	21588 KiB

race

//chockolateman

#include<bits/stdc++.h>
// #include "race.h"

using namespace std;

const long long INF = 1e15;

int k,s[200005],depth[200005],ans;
long long val[200005];
set<pair<int,int>> adj[200005];
map<int,int> min_d;

void dfs1(int v,int p)
{
    s[v] = 1;
    for(auto e : adj[v])
    {
        int u = e.first;
        if(u != p)
        {
            dfs1(u,v);
            s[v] += s[u];
        }
    }
}

int centroid(int v,int p,int n)
{
    for(auto e : adj[v])
    {
        int u = e.first;
        if(u != p && 2*s[u] > n)
            return centroid(u,v,n);
    }
    return v;
}

void dfs2(int v,int p,int add)
{
    if(add==0)
    {
        if(min_d.find(k - val[v]) != min_d.end())
            ans = min(ans,depth[v] + min_d[k - val[v]]);
    }
    else
    {
        if(min_d.find(val[v]) == min_d.end() || min_d[val[v]] > depth[v])
            min_d[val[v]] = depth[v];
    }
    if(v != p)
    {
        for(auto e : adj[v])
        {
            int u = e.first;
            int w = e.second;
            if(u != p)
            {
                val[u] = val[v] + w;
                depth[u] = depth[v] + 1;
                dfs2(u,v,add);
            }
        }
    }
    else
    {
        for(auto e : adj[v])
        {
            int u = e.first;
            int w = e.second;
            val[u] = val[v] + w;
            depth[u] = depth[v] + 1;
            dfs2(u,v,0);
            dfs2(u,v,1);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int a,b,w,i = 0 ; i < N-1 ; i++)
    {
        a = H[i][0];
        b = H[i][1];
        a++;
        b++;
        w = L[i];
        adj[a].insert({b,w});
        adj[b].insert({a,w});
    }
    ans = N+1;
    for(int i = 1 ; i <= N ; i++)
    {
        depth[i] = 0;
        val[i] = 0;
        dfs2(i,i,1);
        vector<pair<int,int>> temp;
        for(auto e : adj[i])
            temp.push_back(e);
        for(auto e : temp)
        {
            adj[i].erase(e);
            int u = e.first;
            int w = e.second;
            adj[u].erase({i,w});
        }    
        min_d.clear();
    }
    if(ans==N+1)
        ans = -1;
    return ans;
}

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