Submission #287603

#	Time	Username	Problem	Language	Result	Execution time	Memory
287603		crossing0ver	Race (IOI11_race)	C++17	0 / 100	6 ms	5376 KiB

race

#include<bits/stdc++.h>
//#define int long long 
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
//#include "race.h"
using namespace std;
const int MXN = 1e5+5;
vector<pii> adj[MXN];
int n,k,sz[MXN];
bool vis[MXN],bad[MXN];


int calcsize(int v,int p) {
	sz[v] = 1;
	for (auto i : adj[v]) {
		int to = i.fi;
		if (!bad[to] && to != p) {
			calcsize(to,v);
			sz[v] += sz[to];
		}
	}
	return sz[v];
}

pii MN;
int SZ;
void getcenter(int v,int p) {
	int mxsz = 0,sum = 0;
	for (auto i : adj[v]) {
		int to = i.fi;
		if (to == p || bad[to]) continue;
		getcenter(to,v);
		mxsz = max(mxsz,sz[to]);
		sum += sz[to];
	}
	int adit = SZ - sum - 1;
	mxsz = max(mxsz,adit);
	MN = min(MN,make_pair(mxsz,v));
}

const int MAXK = 1e6+6;
int dis[MAXK + 5];
int ans = INT_MAX;

void get(int v,int p,int depth,int val) {
	if (val > k) return;
	if (dis[k-val] && dis[k - val] + depth - 1 < ans) 
		ans = dis[k-val] + depth - 1;
	for (auto i : adj[v]) {
		int to = i.fi;
		if (p != to && !bad[to])
			get(to,v,depth+1,val + i.se);
	}
}
void upd(int v,int p,int depth,int val,bool flag) {
	if (dis[val] == 0 || dis[val] > depth)
		dis[val] = depth;
	if (flag == 0) dis[val] = 0;
	for (auto i : adj[v]) {
		int to = i.fi;
		if (p!= to && !bad[to])
			upd(to,v,depth+1,val + i.se,flag);
	}
}
void dfs(int v,int p,int depth,bool keep) {
/*	int big = -1,mxsz =- 1,money = -1;
	for (auto i : adj[v]) {
		int to = i.fi;
		if (to != p && mxsz < sz[to]) {
			//	mxsz = sz[to];
			///	big = to;
			//	money = i.se;
		}
	}*/
/*	if (big + 1) {
		get(big,v,depth+1,money);
		upd(big,v,depth+1,money,1);
	}*/
	for (auto i : adj[v]) {
		int to = i.fi;
		if (bad[to]) continue;
		//if (i == p || i == big)
		///	continue;
		get(to,v,2,i.se);
		upd(to,v,2,i.se,1);
	}
	for (auto i : adj[v]) {
		int to = i.fi;
		if (to != p && !bad[to])
			upd(to,v,depth+1,i.se,0);
	}
}
void split(int v){
	bool ok = 0;
	for (auto i : adj[v])
		if (!bad[i.fi]) ok = 1;
	if (ok == 0) return;
	 SZ = calcsize(v,-1);
	MN = {INT_MAX,0};
//	 getcenter(v,-1);
int center = v;
	 //int center = MN.se;
//	calcsize(center,-1);
	dis[0] = 1;
	dfs(center,-1,1,0);
	
	bad[center] = 1;
	for (auto & i : adj[center])
		if (bad[i.fi] == 0)
			split(i.fi);
}
int best_path(int n1, int k1, int H[][2], int L[])
{
	n = n1;
	k = k1;
  for (int i = 0; i< n ;i++) {
  	adj[H[i][0]].pb({H[i][1],L[i]});
  	adj[H[i][1]].pb({H[i][0],L[i]});
  }
  split(0);
  if (ans == INT_MAX) return -1;
  return ans-1;
}

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