| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 750923 |
2023-05-30T14:34:41 Z |
LCJLY |
Race (IOI11_race) |
C++14 |
|
193 ms |
51876 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
vector<pii>adj[200005];
multiset<pii>storage[200005];
int offset[200005];
int dist[200005];
int d[200005];
int k;
int ans=INT_MAX;
void dp(int index, int par){
//cout << index << " visit\n";
storage[index].insert({dist[index],d[index]});
for(auto it:adj[index]){
if(it.first==par) continue;
dist[it.first]=dist[index]+it.second;
d[it.first]=d[index]+1;
//cout << index << " " << it.first << " call\n";
dp(it.first,index);
//cout << index << " " << it.first << " check\n";
//swap
if(storage[it.first].size()>storage[index].size()){
swap(storage[it.first],storage[index]);
}
//check
for(auto it2:storage[it.first]){
int hold=k-it2.first+dist[index]*2;
//cout << hold << " target\n";
pii hold2=*storage[index].lower_bound({hold,0});
if(hold2.first==hold){
ans=min(ans,hold2.second+it2.second-d[index]*2);
//cout << hold2.second<< " " << it2.second << " " << d[index] << "trigger\n";
}
}
//merge
for(auto it2:storage[it.first]){
storage[index].insert(it2);
}
}
//cout << ans << " " << index << " done\n";
}
int best_path(int n, int K, int H[][2], int L[]){
k=K;
for(int x=0;x<n-1;x++){
adj[H[x][0]].push_back({H[x][1],L[x]});
adj[H[x][1]].push_back({H[x][0],L[x]});
//cout << H[x][0] << " " << H[x][1] << " edge\n";
}
dp(0,-1);
if(ans==INT_MAX) return -1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14396 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14316 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14396 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14316 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14372 KB |
Output is correct |
| 19 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 20 |
Incorrect |
8 ms |
14400 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14396 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14316 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14372 KB |
Output is correct |
| 19 |
Incorrect |
193 ms |
51876 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14396 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 10 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14316 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 14 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14400 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14372 KB |
Output is correct |
| 19 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 20 |
Incorrect |
8 ms |
14400 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
