제출 #819857

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

race

#include <bits/stdc++.h>
//#include "factories.h"
//#include "wall.h"
#include "race.h"
#define f first
#define s second
using namespace std; 
const int maxn = 2e5 + 69;
vector<pair<int, int>> g[maxn];
map<int, int> m[maxn];
vector<int> dep(maxn), sum(maxn);
int ans = 1e9;
void dfs(int v,int p) {
	for(auto u : g[v]) {
		if(u.f != p) {
			dep[u.f] = dep[v] + 1;
			sum[u.f] = sum[v] + u.s;
			dfs(u.f, v);
		}
	}
}

void dfs2(int v, int p, int t) {
	m[v][sum[v]] = dep[v];
	for(auto u : g[v]) {
		if(u.f != p) {
			dfs2(u.f, v, t);
			if(m[u.f].size() > m[v].size())
				swap(m[u.f], m[v]);
			for(auto it : m[u.f]) {
				int trazim = t + 2 * sum[v] - sum[it.f];
				if(m[v].count(trazim))
					ans = min(ans, it.s + m[v][trazim] - 2 * dep[v]);
			}
			for(auto it : m[u.f]) {
				if(m[v].count(it.f))
					m[v][it.f] = min(m[v][it.f], it.s);
				else
					m[v][it.f] = it.s;
			}
		}
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	for(int i = 0;i < N - 1;i++) {
		g[H[i][1]].push_back({H[i][0], L[i]});
		g[H[i][0]].push_back({H[i][1], L[i]});
	}
  	dfs(0, -1);
  	dfs2(0, -1, K);
  	if(ans == 1e9)
  		ans = -1;
  	return ans;
}


// signed main()
// {
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);
	// int tt = 1;
	// //cin >> tt;
	// while(tt--) {
		// int n, k;
		// cin >> n >> k;
		// int h[n - 1][2], l[n - 1];
		// for(int i = 0;i < n - 1;i++) 
			// cin >> h[i][0] >> h[i][1] >> l[i];
		// cout << best_path(n, k, h, l);
	// }
   // return 0;
// }

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