| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998634 |
2024-06-14T11:50:14 Z |
AbodeKu |
Race (IOI11_race) |
C++17 |
|
3 ms |
16216 KB |
#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(key + w > K) continue ;
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 == INF) 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;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
