Submission #1281034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281034		trinm01	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include "race.h"
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll oo = 1e18 + 7;  
const int base = 10;

int n, k;
vector<pii> adj[MAXN];

int del[MAXN], sz[MAXN];
void count(int u, int p){
	sz[u]=1;
	for(auto [v, w]:adj[u]){
		if(v==p || del[v]) continue;
		count(v, u);
		sz[u]+=sz[v];
	}
}
int find(int u, int p, int m){
	for(auto [v, w]:adj[u]){
		if(v==p || del[v]) continue;
		if(sz[v]>m/2){
			return find(v, u, m);
		}
	}
	return u;
}
int ans=oo;
int d[MAXN], h[MAXN];
int mp[1000005];
void reset(int u, int p){
	if(d[u]<=1e6){
		mp[d[u]]=oo;
	}
	if(k-d[u]>=0){
		mp[k-d[u]]=oo;
	}
	for(auto [v, w]:adj[u]){
		if(v==p || del[v]) continue;
		h[v]=h[u]+1;
		d[v]=d[u]+w;
		reset(v, u);
	}
}
void dfs1(int u, int p){
	if(k-d[u]>=0){
		ans=min(ans, h[u]+mp[k-d[u]]);
	}
	for(auto [v, w]:adj[u]){
		if(v==p || del[v]) continue;
		h[v]=h[u]+1;
		d[v]=d[u]+w;
		dfs1(v, u);
	}
}
void dfs2(int u, int p){
	if(d[u]<=1e6)
		mp[d[u]]=min(mp[d[u]], h[u]);
	for(auto [v, w]:adj[u]){
		if(v==p || del[v]) continue;
		dfs2(v, u);
	}
}
void solve(int u){
	h[u]=d[u]=0;
	reset(u, 0);
	mp[0]=0;
	for(auto [v, w]:adj[u]){
		if(del[v]) continue;
		h[v]=h[u]+1;
		d[v]=d[u]+w;
		dfs1(v, u);
		dfs2(v, u);
	}
	
	
	reset(u, 0);
	mp[0]=0;
	FOD(i, (int)adj[u].size()-1, 0){
		auto [v, w]=adj[u][i];
		if(del[v]) continue;
		h[v]=h[u]+1;
		d[v]=d[u]+w;
		dfs1(v, u);
		dfs2(v, u);
	}
}
void centroid(int u, int p){
	count(u, 0);
	int root=find(u, 0, sz[u]);
	
	solve(root);
	
	del[root]=1;
	for(auto [v, w]:adj[root]){
		if(del[v]) continue;
		centroid(v, root);
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	n=N, k=K;
	FOR(i, 0, n-2){
		int u, v, c;
		u=H[i][0];
		v=H[i][1];
		c=L[i];
		u++;
		v++;
		adj[u].push_back({v, c});
    	adj[v].push_back({u, c});
	}
	
	centroid(1, 0);
    
    if(ans==oo) ans=-1;
    cout << ans;
    
    return ans;
}

Compilation message (stderr)

race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:2:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
    1 | #include "race.h"
  +++ |+#include <utility>
    2 | using namespace std;
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: error: 'pair' was not declared in this scope
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:10:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
   10 | #define pii pair<int, int>
      |             ^~~~
race.cpp:18:8: note: in expansion of macro 'pii'
   18 | vector<pii> adj[MAXN];
      |        ^~~
race.cpp:18:1: error: 'vector' does not name a type
   18 | vector<pii> adj[MAXN];
      | ^~~~~~
race.cpp: In function 'void count(long long int, long long int)':
race.cpp:23:25: error: 'adj' was not declared in this scope
   23 |         for(auto [v, w]:adj[u]){
      |                         ^~~
race.cpp: In function 'long long int find(long long int, long long int, long long int)':
race.cpp:30:25: error: 'adj' was not declared in this scope
   30 |         for(auto [v, w]:adj[u]){
      |                         ^~~
race.cpp: In function 'void reset(long long int, long long int)':
race.cpp:48:25: error: 'adj' was not declared in this scope
   48 |         for(auto [v, w]:adj[u]){
      |                         ^~~
race.cpp: In function 'void dfs1(long long int, long long int)':
race.cpp:57:21: error: 'min' was not declared in this scope
   57 |                 ans=min(ans, h[u]+mp[k-d[u]]);
      |                     ^~~
race.cpp:59:25: error: 'adj' was not declared in this scope
   59 |         for(auto [v, w]:adj[u]){
      |                         ^~~
race.cpp: In function 'void dfs2(long long int, long long int)':
race.cpp:68:26: error: 'min' was not declared in this scope
   68 |                 mp[d[u]]=min(mp[d[u]], h[u]);
      |                          ^~~
race.cpp:69:25: error: 'adj' was not declared in this scope
   69 |         for(auto [v, w]:adj[u]){
      |                         ^~~
race.cpp: In function 'void solve(long long int)':
race.cpp:78:25: error: 'adj' was not declared in this scope
   78 |         for(auto [v, w]:adj[u]){
      |                         ^~~
race.cpp:89:21: error: 'adj' was not declared in this scope
   89 |         FOD(i, (int)adj[u].size()-1, 0){
      |                     ^~~
race.cpp:7:36: note: in definition of macro 'FOD'
    7 | #define FOD(i, r, l) for (int i = (r); i >= (l); i--)
      |                                    ^
race.cpp: In function 'void centroid(long long int, long long int)':
race.cpp:105:25: error: 'adj' was not declared in this scope
  105 |         for(auto [v, w]:adj[root]){
      |                         ^~~
race.cpp: In function 'long long int best_path(long long int, long long int, long long int (*)[2], long long int*)':
race.cpp:121:17: error: 'adj' was not declared in this scope
  121 |                 adj[u].push_back({v, c});
      |                 ^~~
race.cpp:128:5: error: 'cout' was not declared in this scope
  128 |     cout << ans;
      |     ^~~~
race.cpp:2:1: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
    1 | #include "race.h"
  +++ |+#include <iostream>
    2 | using namespace std;