Submission #998665

#	Time	Username	Problem	Language	Result	Execution time	Memory
998665		AbodeKu	Race (IOI11_race)	C++17	100 / 100	334 ms	88896 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> PII ;
typedef vector<bool> vb ;
typedef vector<ll> vi;
typedef vector<PII> vpi;
typedef vector<vector<ll>> vvi;
typedef vector<vector<PII>> vvpi;
typedef vector<char> vc ;
 
const double EBS = 1e-9;
const double pi = 3.14159265358979 ;

 
#define Log(x) (31^__builtin_clz(x)) 
#define logll(x) (63^__builtin_clzll(x))
 
// processor cycle counter can be used to get a random number easily :)
#define rand __builtin_ia32_rdtsc() 
 
	
 
#define popcount(i) __builtin_popcount(i)
#define popcountll(i) __builtin_popcountll(i)
 
 
#define mp make_pair
 
 
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs"  << "\n";
 
#define testCase ll t; cin >> t; while (t--)
#define fast  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(f, s, i) for (ll i = f; (int) i < s; i++)
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define calunique(v)  disance(v.begin(),unique(v.begin(),v.end()));
#define el cout << endl
#define pb push_back
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define all(v) v.begin(), v.end()
#define INF (ll) 1e9
#define INFLL (ll)1e18
#define debug cout << "\n___________________________________\n" 
// #define int ll	
 
#define Left  ((p << 1) + 1) 
#define Right ((p << 1) + 2)
const int N = 2e5 + 9 ;
int K ;
vpi adj[N];
int sum[N] , depth[N] ;
vector< map<int , int> > cnt(N);
int ans = 0 ;
void dfs_depth(int node , int par){
	for(auto [nd , w] : adj[node]){
		if(nd != par){
			depth[nd] = depth[node] + 1 ; 
			sum[nd] = sum[node] + w ;
			dfs_depth(nd , node);
		}
	}
}
void dfs(int node , int par){
	for(auto [nd , w] : adj[node]){
		if(nd != par) dfs(nd , node);
	}
	int target = K + 2 * sum[node];
	cnt[node][sum[node]] = depth[node] ;
	for(auto [nd , w] : adj[node]){
		if(nd != par){
			if(cnt[nd].size() > cnt[node].size()) swap(cnt[nd] , cnt[node]);
			for(auto [key , val] : cnt[nd]){
				int find = target - key ;
				/*cout << target << " " << find << " " << key << endl ;*/
				if(cnt[node].find(find) != cnt[node].end()){
					// debug ;
					ans = min(ans , val + cnt[node][find] - 2*depth[node]);
				}
			}
			for(auto [key , val] : cnt[nd]){
				if(cnt[node].find(key) != cnt[node].end()){
					cnt[node][key] = min(cnt[node][key] , val);
				}else{
					cnt[node][key] = val ;
				}
			}
		}
	}
}
int best_path(int n , int k , int (*edges)[2] , int *weights){
	K = k ;
	rep(0 , n-1 , i){
		auto [u , v] = mp(edges[i][0] , edges[i][1]);
		adj[u].pb(mp(v , weights[i]));
		adj[v].pb(mp(u , weights[i]));
	}
	
	ans = INF ; 
	dfs_depth(0 , 0);
	dfs(0 , 0) ;
	if(ans == INF) ans = -1 ;
	return ans;
}

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