제출 #1322273

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

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
int i, j, ans, tot, t, k, total, len, sz[500007]; long long int dis;
multiset<int> s[1000007];
vector<pair<int, int>> tem;
vector<pair<int, int>> v[500007];
bool c[500007];

void dfs(int cu, int pa){
 sz[cu] = 1;
 for(pair<int, int> z: v[cu]){
 if(c[z.first] == 0 || z.first == pa) continue;
 dfs(z.first, cu); sz[cu] += sz[z.first];
 }
}

int dfs_cen(int cu, int pa){
 for(pair<int, int> z: v[cu]){
 if(c[z.first] == 0 || z.first == pa) continue;
 if(sz[z.first] > tot/2) return dfs_cen(z.first, cu);
 }
 return cu;
}

void dfsc(int cu, int pa){
 if(dis > k) return;
 s[dis].insert(len);
 len++;
 for(pair<int, int> z: v[cu]){
 if(c[z.first] == 0 || z.first == pa) continue;
 dis += z.second;
 dfsc(z.first, cu);
 dis -= z.second;
 } len--;
}

void dfsc2(int cu, int pa){
 if(dis > k) return;
 s[dis].clear();
 for(pair<int, int> z: v[cu]){
 if(c[z.first] == 0 || z.first == pa) continue;
 dis += z.second;
 dfsc2(z.first, cu);
 dis -= z.second;
 }
}

void dfsgetp(int cu, int pa){
 if(dis > k) return;
 tem.push_back({dis, len});
 len++;
 for(pair<int, int> z: v[cu]){
 if(c[z.first] == 0 || z.first == pa) continue;
 dis += z.second;
 dfsgetp(z.first, cu);
 dis -= z.second;
 } len--;
}

void get(int in){
 dfs(in, -1); tot = sz[in];

 int cen = dfs_cen(in, -1);

 dis = 0; len = 0; dfsc(cen, -1);

 for(pair<int, int> z: v[cen]){
 if(c[z.first] == 0) continue;
 dis = z.second; len = 1;
 dfsgetp(z.first, cen);
 for(pair<int, int> x: tem) s[x.first].erase(s[x.first].find(x.second));
 for(pair<int, int> x: tem){
 if(!s[k-x.first].empty())
 ans = min(ans, x.second+(*s[k-x.first].begin()));
 }
 for(pair<int, int> x: tem) s[x.first].insert(x.second);
 tem.clear();
 }
 dis = 0; dfsc2(cen, -1);
 c[cen] = 0;
 for(pair<int, int> z: v[cen]) if(c[z.first]) get(z.first);
}

int best_path(int N, int K, int H[][2], int L[]){
 ans = 1e9; k = K;
 for( i = 0; i < N; i++) c[i] = 1;
 for( 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]});
 }
 get(0);
 if(ans == 1e9) ans = -1;
 return ans;
}

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