제출 #278035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
278035		abyyskit	경주 (Race) (IOI11_race)	C++14	100 / 100	2190 ms	204052 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back



int ANS;
int K;
struct node{
	set<pair<int, int>> e;
	map<int, int> m;
	int c = 0;

};

vector<node> g;

int cdfs(int start, int par, int tot){
	for(auto nex: g[start].e){
		if (nex.first != par and g[nex.first].c > tot/2){
			return cdfs(nex.first, start, tot);
		}
	}
	return start;
}

int countdfs(int start, int par){
	g[start].c = 1;
	for(auto nex: g[start].e){
		if (nex.first != par){
			g[start].c += countdfs(nex.first, start);
		}
	}
	return g[start].c;
}

int centralise(int start){
//	cout << "Finding centre of " << start << "\n";
	countdfs(start, - 1);
	return cdfs(start, -1,  g[start].c);
}

void dfs2(int start, int par,  int root, int length, int depth){
	if (g[root].m.count(K - length) != 0){
		ANS = min(ANS, depth + g[root].m[K - length]);
//		if (depth + g[root].m[K - length] == 1){
//			cout << start << " " << root << " " << depth << "\n";
//		}
	}
	for(auto nex: g[start].e){
		if (nex.first != par){
			dfs2(nex.first, start, root, length + nex.second, depth + 1);
		}
	}

		
}

void dfs1(int start, int par, int root, int length, int depth){
	if (g[root].m.count(length) == 0){
		g[root].m[length] = depth;
	}
//	cout << "adding " << length << " " <<  depth << " " << root << "\n";
	g[root].m[length] = min(g[root].m[length],depth);
//	cout << "g[root].m[length] = " << g[root].m[length] << "\n";
	for(auto nex: g[start].e){
		if (nex.first != par){
			dfs1(nex.first, start, root, length + nex.second, depth + 1);
		}
	}


}

void process(int start){
	g[start].m[0] = 0;
	//assumes start is a centroid
//	cout << "processing: " << start << "\n";
	vector<int> do_later;
	for(auto edge: g[start].e){
		g[edge.first].e.erase({start, edge.second});
		dfs2(edge.first, start,  start, edge.second, 1);
		dfs1(edge.first, start, start, edge.second, 1);
//		cout << "ANS = " << ANS << "\n";
//		cout << "Looking into " << edge.first << "\n";
		process(centralise(edge.first));
	}
//	cout << "Finished: " << start << "\n";
}


int best_path(int N, int k, int H[][2], int L[]){
	g.resize(N);
	K = k;
	ANS = N+1;
	FOR(i, 0, N - 1){
		g[H[i][0]].e.insert({H[i][1], L[i]});
		g[H[i][1]].e.insert({H[i][0], L[i]});
	}
	process(centralise(0));
	if (ANS == N + 1){
		ANS = -1;
	}
	return ANS;

}

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