제출 #1201434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201434		jahongir	Race (IOI11_race)	C++20	0 / 100	2 ms	4928 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define pi pair<int,int>
#define pb push_back

const int mxn = 2e5+10;
vector<pi> g[mxn];

int n,k;

int sub[mxn];
bitset<mxn> vis;

int getsize(int u, int p){
	sub[u] = 1;
	for(auto [v,w] : g[u]) if(v!=p && !vis[v])
		sub[u] += getsize(v,u);
	return sub[u];
}

int getcen(int u, int p, int sz){
	for(auto [v,w] : g[u]) if(v!=p && !vis[v])
		if(sub[v]<<1 > sz) return getcen(v,u,sz);
	return u;
}

map<int,int> mp;

int res = mxn;

void dfs1(int u, int p, int dis, int cnt){
	if(dis>k) return;
	if(mp.count(k-dis))
		res = min(res,mp[k-dis]+cnt);
	for(auto [v,w] : g[u]) if(v!=p && !vis[v])
		dfs1(v,u,dis+w,cnt+1);
}

void dfs2(int u, int p, int dis, int cnt){
	if(dis>k) return;
	if(mp.count(dis))
		mp[dis] = min(mp[dis],cnt);
	else mp[dis] = cnt;
	for(auto [v,w] : g[u]) if(v!=p && !vis[v])
		dfs2(v,u,dis+w,cnt+1);
}


void centroid(int u){
	u = getcen(u,u,getsize(u,u));
	mp[0] = 0, vis[u] = 1;


	for(auto [v,w] : g[u]) if(!vis[v]){
		dfs1(v,u,w,1);
		dfs2(v,u,w,1);
	}

	mp.clear();

	for(auto [v,w] : g[u]) if(!vis[v])
		centroid(u);

}

int best_path(int N, int K, int h[][2], int l[]){
	n = N, k = K;
	for(int i = 0; i < n-1; i++){
		g[h[i][0]+1].pb({h[i][1]+1,l[i]});
		g[h[i][1]+1].pb({h[i][0]+1,l[i]});
	}

	if(res==mxn) return -1;
	return res;

}

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