Submission #998632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998632	2024-06-14T11:47:52 Z	AbodeKu	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

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];
vector< map<int , int> > cnt(N);
int ans = 0 ;
void dfs(int node , int par){
	for(auto [nd , w] : adj[node]){
		if(nd != par) dfs(nd , node);
	}
	cnt[node][0] = 0 ;
	for(auto [nd , w] : adj[node]){
		if(nd != par){
			if(cnt[node].size() < cnt[nd].size()) swap(cnt[node] , cnt[nd]);
			for(auto [key , val] : cnt[nd]){
				int find = K - key - w; 
				// cout << key << " " << val << " " << find << endl ;
				if(cnt[node].find(find)  != cnt[node].end()){
					ans = min(ans , val + 1 + cnt[node][find]);
				}
			}
			for(auto [key , val] : cnt[nd]){
				if(cnt[node].find(key+w) == cnt[node].end())
					cnt[node][key + w] = val + 1 ;
				else
					cnt[node][key + w] = min(cnt[node][key + w] , val + 1);
			}
		}
	}
}
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(0 , 0) ;
	if(ans == INFLL) ans = -1 ;
	return ans;
}

int32_t main(){
	fast ;
	int n , k ; cin >> n >> k ;
	int edges[n + 1][2] , weights[n] ;
	rep(0 , n-1 , i){
		cin >> edges[i][0] >> edges[i][1];
	}
	rep(0 , n-1 , i){
		cin >> weights[i] ;
	}
	cout << best_path(n , k ,edges , weights);
	return 0;
}

Compilation message

/usr/bin/ld: /tmp/cc4rrxXk.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccd8U2hm.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status