Submission #206001

#	Time	Username	Problem	Language	Result	Execution time	Memory
206001		jasony123123	Race (IOI11_race)	C++11	0 / 100	3074 ms	9592 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) {
	root = getCentroid(root, -1);

	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());
		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);
			else
				if(table.find(LN-pp.first) != table.end())
					minn(ans, pp.second + *table[LN-pp.first].begin());
		}

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

	for (auto subt : adj[root]) {
		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)
		add_edge(H[i][0], H[i][1], L[i]);
	LN = K;
	dfsSolve(0);
	return ans;
}

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