제출 #1274635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274635		almaz	경주 (Race) (IOI11_race)	C++20	21 / 100	3091 ms	18220 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ar array

const int MOD = 1e9 + 7,INF = 1e9, N = 2e5 + 5;
int n , k, ans = INF;
vector <vector<pair<int,int>>> g;
vector <int> del, sub_sz;
map <int,int> mp;
vector <pair<int,int>> sum;

void dfs(int v,int p){
	sub_sz[v] = 1;
	for(auto [i , c] : g[v]){
		if(i == p || del[i]) continue;
		
		dfs(i , v);
		sub_sz[v] += sub_sz[i];
	}
}

int cent(int v, int p, int m){
	// cout<<"HERE "<<v<<endl;
	for(auto [i , c] : g[v]){
		if(sub_sz[i] * 2 > m && !del[i] && i != p){
			return cent(i, v, m);
		}
	}
	return v;
}

void bfs(int x, int p){
	for(auto [i , c] : g[x]){
		if(i == p || del[i]) continue;
		
		sum[i].ff = sum[x].ff + c;
		sum[i].ss = sum[x].ss + 1;
		int h = k - sum[i].ff;
		if(h >= 0 && h <= k){
			if(h != 0 && mp[h] == 0){
				
			}
			else{
				ans = min(ans , mp[h] + sum[i].ss);
			}
		}
		bfs(i, x);
	}
}

void add(int x , int p){
	for(auto [i , c] : g[x]){
		if(i == p || del[i]) continue;
		if(sum[i].ff <= k && sum[i].ff >= 0){ 
			if(mp[sum[i].ff] == 0 && sum[i].ff != 0) mp[sum[i].ff] = INF;
			mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
		}
		add(i , x);
	}
}

void dec(int v){
	dfs(v , v);
	
	int m = sub_sz[v];
	
	int cen = cent(v, v , m);
	
	map <int,int> mp1;
	
	swap(mp , mp1);
	
	sum.clear();
	sum.resize(n);
	
	mp[0] = 0;
	
	for(auto [i , c] : g[cen]){
		if(del[i] && i == cen) continue;
		sum[i].ff = c;
		sum[i].ss = 1;
		bfs(i , cen);
		int h = k - sum[i].ff;
		if(h >= 0 && h <= k){
			if(h != 0 && mp[h] == 0){
			}
			else {
				ans = min(ans , mp[h] + sum[i].ss);
			}
		}	
		if(sum[i].ff <= k){
			if(mp[sum[i].ff] == 0 && sum[i].ff != 0) mp[sum[i].ff] = INF;
			mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
		}
		add(i, cen);
	}
	
	del[cen] = 1;
	for(auto [i , c] : g[cen]){
		if(del[i]) continue;
		dec(i);
	}
}

int best_path(int N1, int K, int H[][2], int L[]){
	n = N1;
	k = K;
	ans = INF;
	g.clear();
	del.clear();
	sub_sz.clear();
	g.resize(n);
	del.resize(n);
	sub_sz.resize(n);
	
	for(int i = 0;i < n - 1;i++){
		int a = H[i][0], b = H[i][1] , c = L[i];
		
		g[a].pb({b , c});
		g[b].pb({a , c});
	}
	
	
	dec(0);
	
	if(ans == INF){
		return -1;
	}
	return ans;
}

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