Submission #369965

#	Time	Username	Problem	Language	Result	Execution time	Memory
369965		Pulgster	Race (IOI11_race)	C++17	21 / 100	3083 ms	21220 KiB

race

#include "race.h"
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ed <<endl;
int N;
int K;
int cur = -1;
const int mxn = 200005;
vector<vector<pair<int, int>>> adj(mxn);
vector<int> sz(mxn);
vector<int> forb(mxn);
int findCentroid(int n, int node, int par){
	// cerr << imie(node) imie(par) ed;
	if(n == 1){
		cur = node;
		return 0;
	}
 	sz[node] = 1;
 	bool ok = 1;
 	for(int i=0;i<(int)adj[node].size();i++){
 		if(cur != -1){
 			return 0;
 		}
 		int v=adj[node][i].first;
 		assert(v < forb.size());
 		if(v != par && !forb[v]){
 			sz[node] += findCentroid(n, v, node);
 			if(cur != -1){
 				return 0;
 			}
 			if(sz[v] > n / 2) ok = 0;
 		}
 	}
 	if(n - sz[node] > n / 2){
 		ok = 0;
 	}
 	if(ok){
 		cur = node;
 	}
 	return sz[node];
}
 
int ans = 2e5+5;
void dfs(int node, int par, int dist, int cost, map<int, int> &global, vector<pair<int, int>> &local){
	int k=K;
	if(cost == k){
		ans = min(ans, dist);
	}
	if(k-cost > 0 && global[k-cost] != 0){
		ans = min(ans, global[k-cost]+dist);
	}
	for(int i=0;i<(int)adj[node].size();i++){
		int v = adj[node][i].first;
		if(node == cur){
			vector<pair<int, int>> their;
			dfs(v,node,dist+1,cost+adj[node][i].second, global, their);
			for(pair<int, int> j : their){
				if(global[j.first] == 0){
					global[j.first] = j.second;
				}
				global[j.first] = min(global[j.first], j.second);
			}
			continue;
		}
		if(!forb[v] && v != par){
			dfs(v,node,dist+1,cost+adj[node][i].second, global, local);
		}
	}
	local.push_back({cost, dist});
}
void mysol(int node){
	int cnt = 0;
	if(forb[node]){
		return;
	}
	function<void(int, int)> mdfs = [&](int curnode, int par){
		cnt++;
		assert(curnode < adj.size());
		for(int i=0;i<(int)adj[curnode].size();i++){
			int v = adj[curnode][i].first;
			assert(v < forb.size());
			if(!forb[v] && v != par){
				mdfs(v, curnode);
			}
		}
	};
	if(cnt == 1){
		return;
	}
	mdfs(node, -1);
	map<int, int> global;
	cur = -1;
	findCentroid(cnt, node, -1);
	forb[cur] = 1;
	vector<pair<int, int>> local;
	dfs(cur, -1, 0, 0, global, local);
	// cerr << imie(cur) imie(cnt) ed;
	int me = cur;
	assert(me != -1);
	for(int i=0;i<(int)adj[me].size();i++){
		int v = adj[me][i].first;
		if(!forb[v]){
			mysol(v);
		}
	}
}
int best_path(int n, int k, int h[][2], int l[]){
	N=n;
	K=k;
 	for(int i =0;i<n-1;i++){
 		int u = h[i][0];
 		int v = h[i][1];
 		adj[u].push_back({v, l[i]});
 		adj[v].push_back({u, l[i]});
 	}
 	mysol(0);
 	return (ans > n ? -1 : ans);
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from race.cpp:2:
race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:27:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    assert(v < forb.size());
      |           ~~^~~~~~~~~~~~~
race.cpp: In lambda function:
race.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   assert(curnode < adj.size());
      |          ~~~~~~~~^~~~~~~~~~~~
race.cpp:83:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    assert(v < forb.size());
      |           ~~^~~~~~~~~~~~~

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