| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 972966 |
2024-05-01T11:02:11 Z |
RyaroX |
Race (IOI11_race) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
using namespace std;
typedef int ll;
vector <pair <ll, ll> > ND[200005];
ll A[200005];
queue <pair <ll, ll> > Q;
ll P, PV;
vector <pair <ll, ll> > NG;
ll find_mp(ll k, ll pk, ll n){
vector <pair <ll, ll> > PG;
ll m=0, s=0;
for (ll i=0; i<ND[k].size(); i++) {
ll nk = ND[k][i].first;
if (pk == nk or A[nk]) continue;
ll v = find_mp(nk, k, n);
m = max(m, v);
s += v;
PG.push_back({nk, v});
}
if(pk!=-1){
m = max(m, n-s-1);
PG.push_back({pk, n-s-1});
}
//cout<<k<<" "<<s<<" "<<m<<"\n";
if (PV>m) {
PV = m;
P = k;
NG = move(PG);
}
return s+1;
}
ll M[1000005];
ll rez = INT_MAX;
vector <pair<ll,ll> > V;
void path(ll id, ll pid, ll v, ll d){
if(v>=K) return;
//cout<<id<<" "<<v<<" "<<d<<"\n" ;
V.push_back({v,d});
if(M[K-v]!=INT_MAX) rez = min(rez, M[K-v]+d);
for(ll i=0; i<ND[id].size(); i++){
ll nid = ND[id][i].first;
ll nv = ND[id][i].second;
if(pid == nid or A[nid]) continue;
path(nid, id, v+nv, d+1);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
for(ll i=0;i<n-1;i++){
ND[H[i][0]].push_back({H[i][1], L[i]});
ND[H[i][1]].push_back({H[i][0], L[i]});
}
Q.push({0, n});
while (!Q.empty()){
PV=INT_MAX;
ll sz = Q.front().second;
find_mp(Q.front().first, -1, sz);
Q.pop();
A[P] = 1;
for (ll i=0; i<NG.size(); i++){
if(NG[i].second>1)Q.push({NG[i].first, NG[i].second});
}
//cout<<P<<"\n";
for(ll i=0; i<=K; i++){
M[i] = INT_MAX;
}
M[0]=0;
for(ll i=0; i<ND[P].size(); i++){
ll ni = ND[P][i].first;
ll nv = ND[P][i].second;
path(ni, -1, nv, 1);
for(ll j=0; j<V.size(); j++) M[V[j].first]=min(M[V[j].first], V[j].second);
V.clear();
}
//for(ll i=0;i<=K;i++) cout<<(M[i]==INT_MAX?-1:M[i])<<" "; cout<<"\n";
//cout<<rez<<"\n__________\n";
}
return rez==INT_MAX?-1:rez;
}
void read_input()
{
int i;
scanf("%d %d",&N,&K);
//cout<<N<<" "<<K<<"\n";
for(i=0; i<N-1; i++)
scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]);
//cout<<"hello\n";
}
int main()
{
//freopen("in.txt", "r", stdin);
int ans;
read_input();
ans = best_path(N,K,H,L);
printf("%d\n", ans);
return 0;
}
Compilation message
race.cpp: In function 'll find_mp(ll, ll, ll)':
race.cpp:26:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (ll i=0; i<ND[k].size(); i++) {
| ~^~~~~~~~~~~~~
race.cpp: In function 'void path(ll, ll, ll, ll)':
race.cpp:56:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(ll i=0; i<ND[id].size(); i++){
| ~^~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:78:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (ll i=0; i<NG.size(); i++){
| ~^~~~~~~~~~
race.cpp:87:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(ll i=0; i<ND[P].size(); i++){
| ~^~~~~~~~~~~~~
race.cpp:91:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(ll j=0; j<V.size(); j++) M[V[j].first]=min(M[V[j].first], V[j].second);
| ~^~~~~~~~~
race.cpp: In function 'void read_input()':
race.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d %d",&N,&K);
| ~~~~~^~~~~~~~~~~~~~~
race.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccEaXHYJ.o: in function `read_input()':
race.cpp:(.text+0x50): multiple definition of `read_input()'; /tmp/ccb49vpJ.o:grader.cpp:(.text+0x0): first defined here
/usr/bin/ld: /tmp/ccEaXHYJ.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccb49vpJ.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
