Submission #399070

#	Time	Username	Problem	Language	Result	Execution time	Memory
399070		Petremol	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

int n,k;
vector <pair<int,int>> adj[N];
vector <int> sz(N);
vector <bool> mrk(N);

int sdfs(int c,int pre=0){
	sz[c]=1;
	for(auto x:adj[c]){
		if(x.fi==pre||mrk[x.fi]) continue;
		sz[c]+=sdfs(x.fi,c);
	}
	return sz[c];
}

int get(int c,int pre,int s){
	for(auto x:adj[c]){
		if(x.fi==pre||mrk[x.fi]) continue;
		if(2*sz[x.fi]>s) return get(x.fi,c,s);
	}
	return c;
}

map <int,int> cmp;

void dfs(int c,int pre,int d,int cur){
	if(cur>k) return;
	for(auto x:adj[c]){
		if(x.fi==pre||mrk[x.fi]) continue;
		dfs(x.fi,c,d+1,cur+x.se);
	}
	cmp[cur]=d;
}

int ans=inf;

void centroid(int c){
	c=get(c,0,sdfs(c));
	mrk[c]=1;

	map<int,int> mp;
	mp[0]=0;

	for(auto x:adj[c]) if(!mrk[x.fi]){
		dfs(x.fi,c,1,x.se);
		if(mp.size()<cmp.size()) swap(mp,cmp);
		for(auto e:cmp) if(mp.count(k-e.fi)) ans=min(ans,e.se+mp[k-e.fi]);
		for(auto e:cmp){
			if(mp.count(e.fi)) mp[e.fi]=min(mp[e.fi],e.se);
			else mp[e.fi]=e.se;
		}
		cmp.clear();
	}

	for(auto x:adj[c]) if(!mrk[x.fi]) centroid(x.fi);
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N;k=K;
	for(int i=0;i<n-1;i++){
		int u=H[i][0],v=H[i][1],w=L[i];
		++u;++v;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	centroid(1);
	return((ans!=inf)?ans:-1);
}

Compilation message (stderr)

race.cpp:2:1: error: 'vector' does not name a type
    2 | vector <pair<int,int>> adj[N];
      | ^~~~~~
race.cpp:3:1: error: 'vector' does not name a type
    3 | vector <int> sz(N);
      | ^~~~~~
race.cpp:4:1: error: 'vector' does not name a type
    4 | vector <bool> mrk(N);
      | ^~~~~~
race.cpp: In function 'int sdfs(int, int)':
race.cpp:7:2: error: 'sz' was not declared in this scope
    7 |  sz[c]=1;
      |  ^~
race.cpp:8:13: error: 'adj' was not declared in this scope
    8 |  for(auto x:adj[c]){
      |             ^~~
race.cpp:9:17: error: 'mrk' was not declared in this scope
    9 |   if(x.fi==pre||mrk[x.fi]) continue;
      |                 ^~~
race.cpp: In function 'int get(int, int, int)':
race.cpp:16:13: error: 'adj' was not declared in this scope
   16 |  for(auto x:adj[c]){
      |             ^~~
race.cpp:17:17: error: 'mrk' was not declared in this scope
   17 |   if(x.fi==pre||mrk[x.fi]) continue;
      |                 ^~~
race.cpp:18:8: error: 'sz' was not declared in this scope; did you mean 's'?
   18 |   if(2*sz[x.fi]>s) return get(x.fi,c,s);
      |        ^~
      |        s
race.cpp: At global scope:
race.cpp:23:1: error: 'map' does not name a type
   23 | map <int,int> cmp;
      | ^~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:27:13: error: 'adj' was not declared in this scope
   27 |  for(auto x:adj[c]){
      |             ^~~
race.cpp:28:17: error: 'mrk' was not declared in this scope
   28 |   if(x.fi==pre||mrk[x.fi]) continue;
      |                 ^~~
race.cpp:31:2: error: 'cmp' was not declared in this scope
   31 |  cmp[cur]=d;
      |  ^~~
race.cpp: At global scope:
race.cpp:34:9: error: 'inf' was not declared in this scope; did you mean 'int'?
   34 | int ans=inf;
      |         ^~~
      |         int
race.cpp: In function 'void centroid(int)':
race.cpp:38:2: error: 'mrk' was not declared in this scope
   38 |  mrk[c]=1;
      |  ^~~
race.cpp:40:2: error: 'map' was not declared in this scope
   40 |  map<int,int> mp;
      |  ^~~
race.cpp:40:6: error: expected primary-expression before 'int'
   40 |  map<int,int> mp;
      |      ^~~
race.cpp:41:2: error: 'mp' was not declared in this scope
   41 |  mp[0]=0;
      |  ^~
race.cpp:43:13: error: 'adj' was not declared in this scope
   43 |  for(auto x:adj[c]) if(!mrk[x.fi]){
      |             ^~~
race.cpp:45:16: error: 'cmp' was not declared in this scope
   45 |   if(mp.size()<cmp.size()) swap(mp,cmp);
      |                ^~~
race.cpp:45:28: error: 'swap' was not declared in this scope
   45 |   if(mp.size()<cmp.size()) swap(mp,cmp);
      |                            ^~~~
race.cpp:46:14: error: 'cmp' was not declared in this scope
   46 |   for(auto e:cmp) if(mp.count(k-e.fi)) ans=min(ans,e.se+mp[k-e.fi]);
      |              ^~~
race.cpp:46:44: error: 'min' was not declared in this scope
   46 |   for(auto e:cmp) if(mp.count(k-e.fi)) ans=min(ans,e.se+mp[k-e.fi]);
      |                                            ^~~
race.cpp:47:14: error: 'cmp' was not declared in this scope
   47 |   for(auto e:cmp){
      |              ^~~
race.cpp:48:32: error: 'min' was not declared in this scope
   48 |    if(mp.count(e.fi)) mp[e.fi]=min(mp[e.fi],e.se);
      |                                ^~~
race.cpp:51:3: error: 'cmp' was not declared in this scope
   51 |   cmp.clear();
      |   ^~~
race.cpp:54:13: error: 'adj' was not declared in this scope
   54 |  for(auto x:adj[c]) if(!mrk[x.fi]) centroid(x.fi);
      |             ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:62:3: error: 'adj' was not declared in this scope
   62 |   adj[u].push_back({v,w});
      |   ^~~
race.cpp:66:15: error: 'inf' was not declared in this scope; did you mean 'int'?
   66 |  return((ans!=inf)?ans:-1);
      |               ^~~
      |               int