제출 #1294489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294489		cansu_mutlu	경주 (Race) (IOI11_race)	C++20	100 / 100	370 ms	74820 KiB

race

#include<bits/stdc++.h>
#include "race.h"
//#define int long long 
using namespace std;
const int mxn = 2*1e5+5;
vector<vector<array<int,2>>> a(mxn);
vector<array<int,2>> dist(mxn,{0,0});
// dist 0 = kac node gectik, 1 = toplam dist
map<int,int>  mp[mxn];
 int tt;
int ans = 1e9;
void df(int s,int anne,int d)
{
    if(anne!=-1)
    {
        dist[s] = {dist[anne][0]+1,dist[anne][1]+d};
    }
    for(auto x :a[s])
    {
        if(x[0]==anne) continue;
        df(x[0],s,x[1]);
    }
}
void dfs(int s,int anne)
{
    for(auto i:a[s])
    {
        int x = i[0];

        if(x==anne) continue;
        dfs(x,s);
        if(mp[x].size()>mp[s].size())
        swap(mp[x],mp[s]);
        for(auto x:mp[x])
        {
            //cout <<s <<" "<< x.first << " "<< dist[s][1] << endl;
            if((x.first-dist[s][1])==tt) 
            {
                ans = min(ans,x.second-dist[s][0]);
                //cout <<"111111111111111111  " << x.second-dist[s][0] << endl;
            }
            auto it = mp[s].find(tt-x.first+2*dist[s][1]);
            if(it==mp[s].end()) continue;
            //cout << x.first << endl;
            ans = min(ans,it->second+x.second-2*dist[s][0]);
        }
        
        for(auto k:mp[x])
        {
            if(mp[s].count(k.first)) mp[s][k.first] = min(mp[s][k.first],k.second);
            else mp[s][k.first] = k.second;
        }
        
    }
    if(mp[s].count(dist[s][1])) mp[s][dist[s][1]] = min(mp[s][dist[s][1]],dist[s][0]);
        else mp[s][dist[s][1]] = dist[s][0];
        auto it = mp[s].find(tt+dist[s][1]);
        if(it!=mp[s].end())
        {
            ans = min(ans,it->second-dist[s][0]);
        }
}
int best_path(int n, int k, int h[][2], int l[])
{
    for(int i=0;i<n-1;i++)
    {
        a[h[i][0]].push_back({h[i][1],l[i]});
        a[h[i][1]].push_back({h[i][0],l[i]});
    }
    tt = k;
    df(0,-1,-1);
    dfs(0,-1);
   if(ans==1e9) return -1;
   return ans;
}

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