Submission #488638

#	Time	Username	Problem	Language	Result	Execution time	Memory
488638		ssense	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

race

#include <bits/stdc++.h>
#include "race.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
vector<vector<pair<int, ll>>> adj;
int n_glob;
ll k_glob;
vint size_sub;
vint del;
 
int calc(int u, int par)
{
	int children = 1;
	for(auto v : adj[u])
	{
		if(del[v.fr] == 0 && (par == -1 || v.fr != par))
		{
			children+=calc(v.fr, u);
		}
	}
	size_sub[u] = children;
	return children;
}
 
int find_centroid(int u, int size, int par)
{
	for(auto v : adj[u])
	{
		if(v.fr != par && del[v.fr] == 0 && size_sub[v.fr] > size)
		{
			return find_centroid(v.fr, size, u);
		}
	}
	return u;
}
 
ll ans = MXL;
 
void assign(int u)
{
	calc(u, -1);
	int centroid = find_centroid(u, size_sub[u] / 2, -1);
	map<int, ll> cnt;
	cnt[0] = 0;
	del[centroid] = 1;
	for(auto x : adj[centroid])
	{
		if(del[x.fr] == 1)
		{
			continue;
		}
		map<int, ll> now;
		queue<pair<pair<int, int>, pair<ll, ll>>> q;
		q.push({{x.fr, centroid}, {x.sc, 1}});
		while(!q.empty())
		{
			int node = q.front().fr.fr;
			int parent = q.front().fr.sc;
			ll length = q.front().sc.fr;
			ll highways = q.front().sc.sc;
			if(now[length] == 0LL)
			{
				now[length] = highways;
			}
			else
			{
				now[length] = min(now[length], highways);
			}
			q.pop();
			for(auto y : adj[node])
			{
				if(del[y.fr] == 0 && y.fr != parent && length+y.sc <= k_glob)
				{
					q.push({{y.fr, node}, {length+y.sc, highways+1}});
				}
			}
		}
		for(auto num : now)
		{
			if(k_glob == num.fr)
			{
				ans = min(ans, num.sc);
			}
			if(k_glob > num.fr && cnt[k_glob-num.fr] != 0)
			{
				ans = min(ans, num.sc+cnt[k_glob-num.fr]);
			}
		}
		for(auto num : now)
		{
			if(cnt[num.fr] == 0)
			{
				cnt[num.fr] = num.sc;
			}
			else
			{
				cnt[num.fr] = min(cnt[num.fr], num.sc);
			}
		}
	}
	for(auto x : adj[u])
	{
		if(del[x.fr] == 0)
		{
			assign(x.fr);
		}
	}
}
 
int best_path(int n, int k, int h[][2],int l[])
{
	ans = MX;
	adj.clear();
	n_glob = n;
	k_glob = k;
	for(int i = 0; i <= n; i++)
	{
		vector<pair<int, ll>> cop;
		adj.pb(cop);
	}
	for(int i = 0; i < n-1; i++)
	{
		adj[h[i][0]].pb({h[i][1], l[i]});
		adj[h[i][1]].pb({h[i][0], l[i]});
	}
	size_sub.clear();
	del.clear();
	size_sub = vint(n+1);
	del = vint(n+1);
	assign(0);
	if(ans == MX)
	{
		return -1;
	}
	return ans;
}
/*
int32_t main(){
	startt
	int n, k;
	cin >> n >> k;
	int h[n-1][2], l[n-1];
	for(int i = 0; i < n-1; i++)
	{
		cin >> h[i][0] >> h[i][1];
	}
	for(int i = 0; i < n-1; i++)
	{
		cin >> l[i];
	}
	cout << best_path(n, k, h, l) << endl;
}
 */
/*
3 3
0 1
0 2
1 1
 
4 3
0 1
1 2
1 3
1 2 4
 
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7#include <bits/stdc++.h>
#include "race.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
vector<vector<pair<int, ll>>> adj;
int n_glob;
ll k_glob;
vint size_sub;
vint del;
 
int calc(int u, int par)
{
	int children = 1;
	for(auto v : adj[u])
	{
		if(del[v.fr] == 0 && (par == -1 || v.fr != par))
		{
			children+=calc(v.fr, u);
		}
	}
	size_sub[u] = children;
	return children;
}
 
int find_centroid(int u, int size, int par)
{
	for(auto v : adj[u])
	{
		if(v.fr != par && del[v.fr] == 0 && size_sub[v.fr] > size)
		{
			return find_centroid(v.fr, size, u);
		}
	}
	return u;
}
 
ll ans = MXL;
 
void assign(int u)
{
	calc(u, -1);
	int centroid = find_centroid(u, size_sub[u] / 2, -1);
	map<int, ll> cnt;
	cnt[0] = 0;
	del[centroid] = 1;
	for(auto x : adj[centroid])
	{
		if(del[x.fr] == 1)
		{
			continue;
		}
		map<int, ll> now;
		queue<pair<pair<int, int>, pair<ll, ll>>> q;
		q.push({{x.fr, centroid}, {x.sc, 1}});
		while(!q.empty())
		{
			int node = q.front().fr.fr;
			int parent = q.front().fr.sc;
			ll length = q.front().sc.fr;
			ll highways = q.front().sc.sc;
			if(now[length] == 0LL)
			{
				now[length] = highways;
			}
			else
			{
				now[length] = min(now[length], highways);
			}
			q.pop();
			for(auto y : adj[node])
			{
				if(del[y.fr] == 0 && y.fr != parent && length+y.sc <= k_glob)
				{
					q.push({{y.fr, node}, {length+y.sc, highways+1}});
				}
			}
		}
		for(auto num : now)
		{
			if(k_glob == num.fr)
			{
				ans = min(ans, num.sc);
			}
			if(k_glob > num.fr && cnt[k_glob-num.fr] != 0)
			{
				ans = min(ans, num.sc+cnt[k_glob-num.fr]);
			}
		}
		for(auto num : now)
		{
			if(cnt[num.fr] == 0)
			{
				cnt[num.fr] = num.sc;
			}
			else
			{
				cnt[num.fr] = min(cnt[num.fr], num.sc);
			}
		}
	}
	for(auto x : adj[u])
	{
		if(del[x.fr] == 0)
		{
			assign(x.fr);
		}
	}
}
 
int best_path(int n, int k, int h[][2],int l[])
{
	ans = MXL;
	adj.clear();
	n_glob = n;
	k_glob = k;
	for(int i = 0; i <= n; i++)
	{
		vector<pair<int, ll>> cop;
		adj.pb(cop);
	}
	for(int i = 0; i < n-1; i++)
	{
		adj[h[i][0]].pb({h[i][1], l[i]});
		adj[h[i][1]].pb({h[i][0], l[i]});
	}
	size_sub.clear();
	del.clear();
	size_sub = vint(n+1);
	del = vint(n+1);
	assign(0);
	if(ans == MXL)
	{
		return -1;
	}
	return ans;
}
/*
int32_t main(){
	startt
	int n, k;
	cin >> n >> k;
	int h[n-1][2], l[n-1];
	for(int i = 0; i < n-1; i++)
	{
		cin >> h[i][0] >> h[i][1];
	}
	for(int i = 0; i < n-1; i++)
	{
		cin >> l[i];
	}
	cout << best_path(n, k, h, l) << endl;
}
 */
/*
3 3
0 1
0 2
1 1
 
4 3
0 1
1 2
1 3
1 2 4
 
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
 */
#include <bits/stdc++.h>
#include "race.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
vector<vector<pair<int, ll>>> adj;
int n_glob;
ll k_glob;
vint size_sub;
vint del;
 
int calc(int u, int par)
{
	int children = 1;
	for(auto v : adj[u])
	{
		if(del[v.fr] == 0 && (par == -1 || v.fr != par))
		{
			children+=calc(v.fr, u);
		}
	}
	size_sub[u] = children;
	return children;
}
 
int find_centroid(int u, int size, int par)
{
	for(auto v : adj[u])
	{
		if(v.fr != par && del[v.fr] == 0 && size_sub[v.fr] > size)
		{
			return find_centroid(v.fr, size, u);
		}
	}
	return u;
}
 
ll ans = MXL;
 
void assign(int u)
{
	calc(u, -1);
	int centroid = find_centroid(u, size_sub[u] / 2, -1);
	map<int, ll> cnt;
	cnt[0] = 0;
	del[centroid] = 1;
	for(auto x : adj[centroid])
	{
		if(del[x.fr] == 1)
		{
			continue;
		}
		map<int, ll> now;
		queue<pair<pair<int, int>, pair<ll, ll>>> q;
		q.push({{x.fr, centroid}, {x.sc, 1}});
		while(!q.empty())
		{
			int node = q.front().fr.fr;
			int parent = q.front().fr.sc;
			ll length = q.front().sc.fr;
			ll highways = q.front().sc.sc;
			if(now[length] == 0LL)
			{
				now[length] = highways;
			}
			else
			{
				now[length] = min(now[length], highways);
			}
			q.pop();
			for(auto y : adj[node])
			{
				if(del[y.fr] == 0 && y.fr != parent && length+y.sc <= k_glob)
				{
					q.push({{y.fr, node}, {length+y.sc, highways+1}});
				}
			}
		}
		for(auto num : now)
		{
			if(k_glob == num.fr)
			{
				ans = min(ans, num.sc);
			}
			if(k_glob > num.fr && cnt[k_glob-num.fr] != 0)
			{
				ans = min(ans, num.sc+cnt[k_glob-num.fr]);
			}
		}
		for(auto num : now)
		{
			if(cnt[num.fr] == 0)
			{
				cnt[num.fr] = num.sc;
			}
			else
			{
				cnt[num.fr] = min(cnt[num.fr], num.sc);
			}
		}
	}
	for(auto x : adj[u])
	{
		if(del[x.fr] == 0)
		{
			assign(x.fr);
		}
	}
}
 
int best_path(int n, int k, int h[][2],int l[])
{
	ans = MXL;
	adj.clear();
	n_glob = n;
	k_glob = k;
	for(int i = 0; i <= n; i++)
	{
		vector<pair<int, ll>> cop;
		adj.pb(cop);
	}
	for(int i = 0; i < n-1; i++)
	{
		adj[h[i][0]].pb({h[i][1], l[i]});
		adj[h[i][1]].pb({h[i][0], l[i]});
	}
	size_sub.clear();
	del.clear();
	size_sub = vint(n+1);
	del = vint(n+1);
	assign(0);
	if(ans == MXL)
	{
		return -1;
	}
	return ans;
}
/*
int32_t main(){
	startt
	int n, k;
	cin >> n >> k;
	int h[n-1][2], l[n-1];
	for(int i = 0; i < n-1; i++)
	{
		cin >> h[i][0] >> h[i][1];
	}
	for(int i = 0; i < n-1; i++)
	{
		cin >> l[i];
	}
	cout << best_path(n, k, h, l) << endl;
}
 */
/*
3 3
0 1
0 2
1 1
 
4 3
0 1
1 2
1 3
1 2 4
 
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
 */

 */

Compilation message (stderr)

race.cpp:347:1: warning: "/*" within comment [-Wcomment]
  347 | /*
      |  
race.cpp:410:31: error: redefinition of 'std::vector<std::vector<std::pair<int, long long int> > > adj'
  410 | vector<vector<pair<int, ll>>> adj;
      |                               ^~~
race.cpp:22:31: note: 'std::vector<std::vector<std::pair<int, long long int> > > adj' previously declared here
   22 | vector<vector<pair<int, ll>>> adj;
      |                               ^~~
race.cpp:411:5: error: redefinition of 'int n_glob'
  411 | int n_glob;
      |     ^~~~~~
race.cpp:23:5: note: 'int n_glob' previously declared here
   23 | int n_glob;
      |     ^~~~~~
race.cpp:412:4: error: redefinition of 'll k_glob'
  412 | ll k_glob;
      |    ^~~~~~
race.cpp:24:4: note: 'll k_glob' previously declared here
   24 | ll k_glob;
      |    ^~~~~~
race.cpp:413:6: error: redefinition of 'std::vector<int> size_sub'
  413 | vint size_sub;
      |      ^~~~~~~~
race.cpp:25:6: note: 'std::vector<int> size_sub' previously declared here
   25 | vint size_sub;
      |      ^~~~~~~~
race.cpp:414:6: error: redefinition of 'std::vector<int> del'
  414 | vint del;
      |      ^~~
race.cpp:26:6: note: 'std::vector<int> del' previously declared here
   26 | vint del;
      |      ^~~
race.cpp:416:5: error: redefinition of 'int calc(int, int)'
  416 | int calc(int u, int par)
      |     ^~~~
race.cpp:28:5: note: 'int calc(int, int)' previously defined here
   28 | int calc(int u, int par)
      |     ^~~~
race.cpp:430:5: error: redefinition of 'int find_centroid(int, int, int)'
  430 | int find_centroid(int u, int size, int par)
      |     ^~~~~~~~~~~~~
race.cpp:42:5: note: 'int find_centroid(int, int, int)' previously defined here
   42 | int find_centroid(int u, int size, int par)
      |     ^~~~~~~~~~~~~
race.cpp:442:4: error: redefinition of 'll ans'
  442 | ll ans = MXL;
      |    ^~~
race.cpp:54:4: note: 'll ans' previously defined here
   54 | ll ans = MXL;
      |    ^~~
race.cpp:444:6: error: redefinition of 'void assign(int)'
  444 | void assign(int u)
      |      ^~~~~~
race.cpp:56:6: note: 'void assign(int)' previously defined here
   56 | void assign(int u)
      |      ^~~~~~
race.cpp:515:5: error: redefinition of 'int best_path(int, int, int (*)[2], int*)'
  515 | int best_path(int n, int k, int h[][2],int l[])
      |     ^~~~~~~~~
race.cpp:127:5: note: 'int best_path(int, int, int (*)[2], int*)' previously defined here
  127 | int best_path(int n, int k, int h[][2],int l[])
      |     ^~~~~~~~~
race.cpp:585:3: error: expected unqualified-id before '/' token
  585 |  */
      |   ^