제출 #369583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369583		Pulgster	Race (IOI11_race)	C++11	0 / 100	3080 ms	6636 KiB

race

#include "race.h"
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> adj(2e5+5);
vector<int> sz(2e5+5);
int N;
int K;
int cur = -1;
vector<int> forb(2e5+5);
int findCentroid(int n, int node, int par){
	if(n == 1){
		cur = node;
		return 0;
	}
 	sz[node] = 1;
 	bool ok = 1;
 	for(int i=0;i<adj[node].size();i++){
 		if(cur != -1){
 			return 0;
 		}
 		int v=adj[node][i].first;
 		if(v != par && !forb[v]){
 			sz[node] += findCentroid(n, v, node);
 			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;
//map<cost, edgecount>
void dfs(int node, int par, int dist, int cost, unordered_map<int, int> &global){
	int k=K;
	if(cost > K){
		return;
	}
	if(cost == k){
		ans = min(ans, dist);
		return;
	}
	if(global[k-cost] != 0){
		ans = min(ans, global[k-cost]+dist);
	}
	for(int i=0;i<adj[node].size();i++){
		int v = adj[node][i].first;
		if(!forb[v] && v != par){
			dfs(v,par,dist+1,cost+adj[node][i].second, global);
		}
	}
	if(global[cost] == 0){
		global[cost] = dist;
	}
	global[cost] = min(global[cost], dist);
}
void solve(int node){
	
	int cnt = 0;
	function<void(int, int)> mdfs = [&](int cur, int par){
		cnt++;
		for(int i=0;i<adj[cur].size();i++){
			int v = adj[cur][i].first;
			if(!forb[v] && v != par){
				mdfs(v, cur);
			}
		}
	};
	mdfs(node, -1);
	unordered_map<int, int> global;
	cur = -1;
	findCentroid(cnt, node, -1);
	forb[cur] = 1;
	dfs(cur, -1, 0, 0, global);
	// cerr << imie(cur) imie(cnt) ed;
	int me = cur;
	for(int i=0;i<adj[me].size();i++){
		int v = adj[me][i].first;
		if(!forb[v]){
			solve(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++){
 		for(int j=0;j<2;j++){
 			adj[h[i][j]].push_back(make_pair(h[i][(j+1)%2], l[i]));
 		}
 	}
 	solve(0);
 	return (ans > n ? -1 : ans);
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i=0;i<adj[node].size();i++){
      |               ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::unordered_map<int, int>&)':
race.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<adj[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~
race.cpp: In lambda function:
race.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i=0;i<adj[cur].size();i++){
      |               ~^~~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<adj[me].size();i++){
      |              ~^~~~~~~~~~~~~~~

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