Submission #848910

#	Time	Username	Problem	Language	Result	Execution time	Memory
848910		ilhan_arda	Race (IOI11_race)	C++17	9 / 100	3052 ms	11348 KiB

race

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "race.h"
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
//#define int long long
using namespace std;
typedef long long ll;
typedef tuple<int, int, int> iii;


int rem, ans=1e9, k;
vector<vector<pair<int, int>>> graph;
vector<int> sub;
map<int, int> sums;
vector<bool> vis, mark;
int dfs1(int node, int par){
	int val= 1;
	mark[node]=true;
	//~ cout<<node<<" :dfs1: "<<par<<endl;
	for(auto it: graph[node]){
		if(it.fi==par)continue;
		if(vis[it.fi])continue;
		val+=dfs1(it.fi, node);
	}
	sub[node]=val;
	return val;
}
void dfs2(int node, int par, int cur, int len){
	if(cur>k)return;
	//~ cout<<node<<" :dfs2: "<<cur<<" :dfs2: "<<len<<endl;
	if(sums[k-cur] || cur==k){
		//~ cout<<"ans "<< ans <<" ans"<<endl;
		ans=min(ans, sums[k-cur]+len);
		//~ cout<<ans<<" :: "<<node<<" :: "<<cur<<" :: "<<len<<endl; 
	}
	for(auto it: graph[node]){
		if(vis[it.fi])continue;
		if(it.fi==par)continue;
		dfs2(it.fi, node, cur+it.se, len+1);
	}
	if(!sums[cur])sums[cur]=len;
	sums[cur]=min(len, sums[cur]);
	return;
}
int findcentroid(int node, int par, int sz){
	for(auto it: graph[node]){
		//~ cout<<"findcentroid"<<endl;
		if(vis[it.fi])continue;
		if(it.fi==par)continue;
		if(sub[it.fi]>=sz){
			return findcentroid(it.fi, node, sz);
		}
	}
	return node;
}

int best_path(int N, int K, int H[][2], int L[])
{
	rem = N;
	k=K;
	graph.assign(N+5, vector<pair<int, int>>());
	vis.assign(N+5, false);
	for(int i=0;i<N-1;i++){
		graph[H[i][1]].pb({H[i][0], L[i]});
		graph[H[i][0]].pb({H[i][1], L[i]});
	}
	while(rem){
		mark.assign(N+5, false);
		//~ sums.assign(1e6+5, -1);
		sub.assign(N+5, 0);
		for(int i=0;i<N;i++){
			//~ sums.assign(1e6+5, -1);
			sums.clear();
			if(mark[i] || vis[i])continue;
			int sz=dfs1(i, -1);
			int centroid=findcentroid(i, -1, sz);
			//~ cout<<centroid<<" ::::: "<<endl;
			dfs2(centroid, -1, 0, 0);
			vis[centroid]=true;
			rem--;
		}
	}
	if(ans==1e9)return -1;
	return ans;
  return N;
}

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