Submission #206002

#	Time	Username	Problem	Language	Result	Execution time	Memory
206002		jasony123123	Race (IOI11_race)	C++11	100 / 100	2895 ms	115544 KiB

race

#include "race.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

// g++ -std=c++11 -Wall -Wextra -O2 -pipe grader.cpp cluedo.cpp -o cluedo && cluedo < grader.in.1

set<pii> adj[200000]; // node, length
int subt_sz[200000];

int dfs_sz(int x, int p) {
	subt_sz[x] = 1;
	for (auto c : adj[x]) if (c.first != p) subt_sz[x] += dfs_sz(c.first, x);
	return subt_sz[x];
}

int getCentroid(int x, int p) {
	dfs_sz(x, p);
	int maxsize = subt_sz[x]/2;
	while (true) {
		int next = -1;
		for (auto c : adj[x]) if (c.first!=p && subt_sz[c.first] > maxsize) {
			next = c.first;
			break;
		}
		if (next == -1) return x;
		p = x, x = next;
	}
	assert(0);
}

int ans = INT_MAX, LN; // min highways, with len = LN

void dfs_subt(int x, int p, int len, int highways, map<int,int> &table){
	if(table.find(len) == table.end()) table[len] = highways;
	else minn(table[len], highways);

	for(auto c : adj[x]) if(c.first != p && len+c.second <= LN)
		dfs_subt(c.first, x, len+c.second, highways+1, table);
}

void dfsSolve(int root) {
	//cout << "initial root = " << root << endl;
	root = getCentroid(root, -1);
	//cout << "centroid  = " << root << endl;


	map<int, multiset<int>> table; // <len, possible highways>
	v<map<int,int>> subdata; // {len, highways}

	for(auto subt : adj[root]){
		subdata.push_back(map<int,int>());
		dfs_subt(subt.first, root, subt.second, 1, subdata.back());
		//cout << "subt " << subt.first << " data " << endl;
	//	for(auto pp : subdata.back())
			//cout << "len " << pp.first << "; highways " << pp.second << endl;

		for(auto pp : subdata.back())
			table[pp.first].insert(pp.second);
	}



	for(auto &subtable : subdata){
		for(auto pp : subtable)
			table[pp.first].erase(table[pp.first].find(pp.second));

		for(auto pp : subtable){
			if(pp.first == LN){
				minn(ans, pp.second);
				//cout << "ans (single) " << pp.second << endl;
			}
			else
				if(table.find(LN-pp.first) != table.end() && table[LN-pp.first].size() > 0){
					minn(ans, pp.second + *table[LN-pp.first].begin());
					//cout << "ans " << (pp.second) << " + " << *table[LN-pp.first].begin() << endl;
				}
		}

		for(auto pp : subtable)
			table[pp.first].insert(pp.second);
	}

	//cout << endl << endl;
	for (auto subt : adj[root]) {
		assert(adj[subt.first].find({root, subt.second}) != adj[subt.first].end());
		adj[subt.first].erase({root, subt.second});
		dfsSolve(subt.first);
	}
}

void add_edge(int a, int b, int c){
	adj[a].insert({b,c});
	adj[b].insert({a,c});
}

int best_path(int N, int K, int H[][2], int L[]){
	FOR(i,0,N-1)
		add_edge(H[i][0], H[i][1], L[i]);

	LN = K;
	dfsSolve(0);
	return (ans == INT_MAX ? -1 : ans);
}

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