Submission #399073

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

race

#include "race.h"
#include <bits/stdc++.h>
#define int long long int
#define all(x) x.begin(), x.end()
#define send ios_base::sync_with_stdio(false);
#define help cin.tie(NULL)
#define inf (int)(1e17+1)
#define mod (int)(1e9+7)
#define N (int)(2e5+5)
#define fi first
#define se second
#define endl "\n"
#define double long double
#define eps (double)(1e-9)
#define sa cout<<"sa"<<endl
using namespace std;

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:9:16: error: 'long long int best_path' redeclared as different kind of entity
    9 | #define N (int)(2e5+5)
      |                ^
race.cpp:74:19: note: in expansion of macro 'N'
   74 | int best_path(int N, int K, int H[][2], int L[]){
      |                   ^
In file included from race.cpp:1:
race.h:1:5: note: previous declaration 'int best_path(int, int, int (*)[2], int*)'
    1 | int best_path(int N, int K, int H[][2], int L[]);
      |     ^~~~~~~~~
race.cpp:3:13: error: expected primary-expression before 'long'
    3 | #define int long long int
      |             ^~~~
race.cpp:74:15: note: in expansion of macro 'int'
   74 | int best_path(int N, int K, int H[][2], int L[]){
      |               ^~~
race.cpp:3:13: error: expected primary-expression before 'long'
    3 | #define int long long int
      |             ^~~~
race.cpp:74:22: note: in expansion of macro 'int'
   74 | int best_path(int N, int K, int H[][2], int L[]){
      |                      ^~~
race.cpp:3:13: error: expected primary-expression before 'long'
    3 | #define int long long int
      |             ^~~~
race.cpp:74:29: note: in expansion of macro 'int'
   74 | int best_path(int N, int K, int H[][2], int L[]){
      |                             ^~~
race.cpp:3:13: error: expected primary-expression before 'long'
    3 | #define int long long int
      |             ^~~~
race.cpp:74:41: note: in expansion of macro 'int'
   74 | int best_path(int N, int K, int H[][2], int L[]){
      |                                         ^~~