Submission #719300

#	Time	Username	Problem	Language	Result	Execution time	Memory
719300		XJP12	경주 (Race) (IOI11_race)	C++14	0 / 100	0 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;
vi indeg;
vi order;
int k1;
bool ban=false;
void dfs(int u){
	vis[u]=true;
	for(auto v: g[u]){
		if(!vis[v.first]){
			if(ban==false) order.push_back(v.first);
			sum+=v.second;
			//cout<<sum<<endl;
			len++;
			if(sum==k1) opt=min(opt,len);
			dfs(v.first);
		}
	}
}
int best_path(int n, int k, int h[][2], int l[]){
	opt=n;
	k1=k;
	vis.resize(n,0);
	indeg.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]));
		indeg[h[i][0]]++;
		indeg[h[i][1]]++;
	}
	int root;
	for(int i=0; i<n-1; i++){
		if(indeg[i]==1) root=i;
	}
	for(int i=0; i<n-1; i++){
		sum=0;
		vis.resize(n,0);
		dfs(root);
		ban=true;
		root=order[i];
	}
	return opt;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:47:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |   dfs(root);
      |   ~~~^~~~~~

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