| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 426287 |
2021-06-13T16:54:00 Z |
SAAD |
Race (IOI11_race) |
C++17 |
|
3000 ms |
11532 KB |
#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
//#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
int n , k ;
bool visa[(int)3 * 100000];
vector <pair<int,int>> x[200002];
int best_path( int N, int K, int H[][2] ,int L[]) {
n = N;k = K;
for ( int i = 0 ; i < n-1 ; i++ ) {
x[H[i][0]].pb( { L[i] , H[i][1] } );
swap(H[i][0],H[i][1]);
x[H[i][0]].pb( { L[i] , H[i][1] } );
}
int mn = (int)1e6;
for ( int i = 0; i < n; i++ ) {
memset(visa,0,sizeof(visa));
queue <pair<ll,int>> q ;
q.push({0,i});
int z = 1 , layer = 0 ;
while ( !q.empty() ) {
if ( layer > k ) break;
int a = q.front().S; ll cst = q.front().F;
q.pop();
visa[a] = true;
cst *= -1 ;
if (cst == k) mn = min(mn,layer);
for (auto i:x[a]) {
if ( visa[i.S] ) continue ;
q.push( { -(cst+i.F) , i.S } );
}
z--;
if ( !z ) {
layer++;
z = q.size();
}
}
}
return (mn==(int)1e6?-1:mn) ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5260 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5260 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 19 |
Correct |
4 ms |
5196 KB |
Output is correct |
| 20 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 21 |
Correct |
32 ms |
5336 KB |
Output is correct |
| 22 |
Correct |
31 ms |
5344 KB |
Output is correct |
| 23 |
Correct |
32 ms |
5324 KB |
Output is correct |
| 24 |
Correct |
31 ms |
5324 KB |
Output is correct |
| 25 |
Correct |
35 ms |
5324 KB |
Output is correct |
| 26 |
Correct |
33 ms |
5268 KB |
Output is correct |
| 27 |
Correct |
31 ms |
5324 KB |
Output is correct |
| 28 |
Correct |
33 ms |
5364 KB |
Output is correct |
| 29 |
Correct |
36 ms |
5324 KB |
Output is correct |
| 30 |
Correct |
32 ms |
5360 KB |
Output is correct |
| 31 |
Correct |
32 ms |
5364 KB |
Output is correct |
| 32 |
Correct |
32 ms |
5324 KB |
Output is correct |
| 33 |
Correct |
32 ms |
5324 KB |
Output is correct |
| 34 |
Correct |
28 ms |
5348 KB |
Output is correct |
| 35 |
Correct |
24 ms |
5324 KB |
Output is correct |
| 36 |
Correct |
27 ms |
5324 KB |
Output is correct |
| 37 |
Correct |
22 ms |
5324 KB |
Output is correct |
| 38 |
Correct |
26 ms |
5352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5260 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 19 |
Execution timed out |
3072 ms |
11532 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5260 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5260 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 19 |
Correct |
4 ms |
5196 KB |
Output is correct |
| 20 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 21 |
Correct |
32 ms |
5336 KB |
Output is correct |
| 22 |
Correct |
31 ms |
5344 KB |
Output is correct |
| 23 |
Correct |
32 ms |
5324 KB |
Output is correct |
| 24 |
Correct |
31 ms |
5324 KB |
Output is correct |
| 25 |
Correct |
35 ms |
5324 KB |
Output is correct |
| 26 |
Correct |
33 ms |
5268 KB |
Output is correct |
| 27 |
Correct |
31 ms |
5324 KB |
Output is correct |
| 28 |
Correct |
33 ms |
5364 KB |
Output is correct |
| 29 |
Correct |
36 ms |
5324 KB |
Output is correct |
| 30 |
Correct |
32 ms |
5360 KB |
Output is correct |
| 31 |
Correct |
32 ms |
5364 KB |
Output is correct |
| 32 |
Correct |
32 ms |
5324 KB |
Output is correct |
| 33 |
Correct |
32 ms |
5324 KB |
Output is correct |
| 34 |
Correct |
28 ms |
5348 KB |
Output is correct |
| 35 |
Correct |
24 ms |
5324 KB |
Output is correct |
| 36 |
Correct |
27 ms |
5324 KB |
Output is correct |
| 37 |
Correct |
22 ms |
5324 KB |
Output is correct |
| 38 |
Correct |
26 ms |
5352 KB |
Output is correct |
| 39 |
Execution timed out |
3072 ms |
11532 KB |
Time limit exceeded |
| 40 |
Halted |
0 ms |
0 KB |
- |
