| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038061 |
2024-07-29T12:36:48 Z |
elotelo966 |
Race (IOI11_race) |
C++17 |
|
2 ms |
8280 KB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <race.h>
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 100005
#define fi first
#define se second
map<int,int> mp;
vector<pair<int,int>> noww;
vector<pair<int,int>> v[lim];
int x[lim],y[lim],l[lim];
int removed[lim],sub_tree[lim];
int cev=LLONG_MAX,k;
inline int find_size(int node,int ata){
sub_tree[node]=1;
for(auto go:v[node]){
if(go.fi==ata || removed[go.fi])continue;
find_size(go.fi,node);
sub_tree[node]+=sub_tree[go.fi];
}
return sub_tree[node];
}
inline int find_centroid(int node,int ata,int cur_size){
for(auto go:v[node]){
if(go.fi==ata || removed[go.fi])continue;
if(sub_tree[go.fi]*2>cur_size)return find_centroid(go.fi,node,cur_size);
}
return node;
}
inline void dfs(int node,int ata,int cur,int sayac){
if(cur>k)return ;
noww.push_back({cur,sayac});
for(auto go:v[node]){
if(go.fi==ata || removed[go.fi])continue;
dfs(go.fi,node,cur+go.se,sayac+1);
}
}
inline void solve(int node){
mp.clear();
mp[0]=0;
for(auto go:v[node]){
if(removed[go.fi])continue;
noww.clear();
dfs(go.fi,node,go.se,1);
for(auto x:noww){
if(mp.find(k-x.fi)==mp.end()){
continue;
}
cev=min(cev,mp[k-x.fi]+x.se);
}
for(auto x:noww){
if(mp.find(x.fi)==mp.end())mp[x.fi]=x.se;
else mp[x.fi]=min(mp[x.fi],x.se);
}
}
}
inline void build(int node){
int cur_size=find_size(node,-1);
int cur_centroid=find_centroid(node,-1,cur_size);
removed[node]=1;
solve(cur_centroid);
for(auto go:v[cur_centroid]){
if(removed[go.fi])continue;
build(go.fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
int n=N;
k=K;
FOR{
if(i==1)continue;
x[i]=H[i-2][0];
y[i]=H[i-2][1];
l[i]=L[i-2];
v[x[i]].push_back({y[i],l[i]});
v[y[i]].push_back({x[i],l[i]});
}
build(1);
if(cev==LLONG_MAX)return -1;
else return cev;
}
/*
int32_t main(){
faster
int n;cin>>n>>k;
FOR{
if(i==1)continue;
cin>>x[i]>>y[i];
}
FOR{
if(i==1)continue;
cin>>l[i];
v[x[i]].push_back({y[i],l[i]});
v[y[i]].push_back({x[i],l[i]});
}
build(1);
if(cev==LLONG_MAX)cout<<-1<<'\n';
else cout<<cev<<'\n';
return 0;
}*/
Compilation message
race.cpp:27:9: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
27 | int cev=LLONG_MAX,k;
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
