Submission #719241

#	Time	Username	Problem	Language	Result	Execution time	Memory
719241		XJP12	경주 (Race) (IOI11_race)	C++14	0 / 100	168 ms	262144 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
vi vis;
vector<vector<pair<int,int>>> g;
int sum=0;
int opt;
int len=0;
void dfs(int u, int j){
	vis[u]=true;
	if(u==j) return;
	for(auto v: g[u]){
		if(!vis[v.first]){
			sum+=v.second;
			len++;
			dfs(u,j);
			sum-=v.second;
			len--;
		}
	}
}
int best_path(int n, int k, int h[][2], int l[]){
	opt=n;
	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]));
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			vis.resize(n,0);
			sum=0;
			len=0;
			dfs(i,j);
			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