제출 #719290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719290		XJP12	경주 (Race) (IOI11_race)	C++14	0 / 100	4 ms	212 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
vi vis;
vector<vector<pair<int,int>>> g;
ll sum=0;
int opt;
int len=0;
int k1;
void dfs(int u, int j, int parent){
	vis[u]=true;
	if(u==j) return;
	for(auto v: g[u]){
		if(!vis[v.first]){
		//	cout<<sum<<endl;
			sum+=v.second;
		//	cout<<sum<<" suma "<<v.first<<endl;
			len++;
			dfs(v.first,j,u);
			if(sum==k1) opt=min(opt,len);
		}
	}
//	sum-=g[parent][u].second;
	//len--;
}
int best_path(int n, int k, int h[][2], int l[]){
	opt=n;
	k1=k;
	vis.resize(n,0);
	vector<pair<int,int>> p;
	g.resize(n,p);
	for(int i=0; i<n-1; i++){
		g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
		g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			vis.assign(n,0);
			sum=0;
			len=0;
			//cout<<i<<" hola "<<j<<endl;
			dfs(i,j,i); 
			//cout<<i<<" "<<j<<" = "<<sum<<endl;
			if(sum==k) opt=min(opt,len);
		}
	}
	return opt;
}

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