# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
28831 |
2017-07-17T09:31:45 Z |
ozaslan |
Race (IOI11_race) |
C++14 |
|
3000 ms |
17200 KB |
#include<bits/stdc++.h>
#include "race.h"
#define MAX_N 500000
#define oo (1<<28)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
/*static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(2==scanf("%d %d",&N,&K));
for(i=0; i<N-1; i++)
my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
freopen("grader.in.3", "r", stdin);
int ans;
read_input();
ans = best_path(N,K,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}*/
vector< pair<int, int> > E[MAX_N];
typedef struct KENAR
{
int dugum, uzunluk, derinlik;
KENAR() {}
KENAR(int d, int u, int de) {dugum = d, uzunluk = u, derinlik = de; }
};
int BFS(int bas, int K, int N) {
bool kul[MAX_N];
for (int i = 0; i < N; i++) kul[i] = 0;
queue<KENAR> Q;
KENAR ilk(bas, 0, 0);
Q.push(ilk);
while ( !Q.empty() ) {
KENAR u = Q.front(); Q.pop();
// if (u.uzunluk == K) return u.derinlik;
kul[u.dugum] = 1;
int s = E[u.dugum].size();
for (int i = 0; i < s; i++) {
int v = E[u.dugum][i].ff, m = E[u.dugum][i].ss;
if (kul[v]) continue;
if (u.uzunluk + m < K) Q.push( KENAR(v, u.uzunluk + m, u.derinlik+1) );
if (u.uzunluk + m == K) return u.derinlik + 1;
}
}
return 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < N-1; i++) {
E[ H[i][0] ].push_back( make_pair( H[i][1], L[i]) );
E[ H[i][1] ].push_back( make_pair( H[i][0], L[i]) );
}
int enIyi = oo, sonuc;
for (int i = 0; i < N; i++) {
sonuc = BFS(i, K, N);
if (sonuc) enIyi = min(enIyi, sonuc);
}
if (enIyi == oo) enIyi = -1;
return enIyi;
}
Compilation message
race.cpp:47:1: warning: 'typedef' was ignored in this declaration
typedef struct KENAR
^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12116 KB |
Output is correct |
2 |
Correct |
11 ms |
12260 KB |
Output is correct |
3 |
Correct |
12 ms |
12260 KB |
Output is correct |
4 |
Correct |
11 ms |
12260 KB |
Output is correct |
5 |
Correct |
11 ms |
12260 KB |
Output is correct |
6 |
Correct |
11 ms |
12260 KB |
Output is correct |
7 |
Correct |
11 ms |
12332 KB |
Output is correct |
8 |
Correct |
12 ms |
12392 KB |
Output is correct |
9 |
Correct |
11 ms |
12392 KB |
Output is correct |
10 |
Correct |
14 ms |
12392 KB |
Output is correct |
11 |
Correct |
14 ms |
12392 KB |
Output is correct |
12 |
Correct |
13 ms |
12392 KB |
Output is correct |
13 |
Correct |
17 ms |
12392 KB |
Output is correct |
14 |
Correct |
14 ms |
12392 KB |
Output is correct |
15 |
Correct |
15 ms |
12392 KB |
Output is correct |
16 |
Correct |
13 ms |
12392 KB |
Output is correct |
17 |
Correct |
15 ms |
12392 KB |
Output is correct |
18 |
Correct |
12 ms |
12392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12116 KB |
Output is correct |
2 |
Correct |
11 ms |
12260 KB |
Output is correct |
3 |
Correct |
12 ms |
12260 KB |
Output is correct |
4 |
Correct |
11 ms |
12260 KB |
Output is correct |
5 |
Correct |
11 ms |
12260 KB |
Output is correct |
6 |
Correct |
11 ms |
12260 KB |
Output is correct |
7 |
Correct |
11 ms |
12332 KB |
Output is correct |
8 |
Correct |
12 ms |
12392 KB |
Output is correct |
9 |
Correct |
11 ms |
12392 KB |
Output is correct |
10 |
Correct |
14 ms |
12392 KB |
Output is correct |
11 |
Correct |
14 ms |
12392 KB |
Output is correct |
12 |
Correct |
13 ms |
12392 KB |
Output is correct |
13 |
Correct |
17 ms |
12392 KB |
Output is correct |
14 |
Correct |
14 ms |
12392 KB |
Output is correct |
15 |
Correct |
15 ms |
12392 KB |
Output is correct |
16 |
Correct |
13 ms |
12392 KB |
Output is correct |
17 |
Correct |
15 ms |
12392 KB |
Output is correct |
18 |
Correct |
12 ms |
12392 KB |
Output is correct |
19 |
Correct |
12 ms |
12392 KB |
Output is correct |
20 |
Correct |
11 ms |
12392 KB |
Output is correct |
21 |
Correct |
33 ms |
12416 KB |
Output is correct |
22 |
Correct |
13 ms |
12416 KB |
Output is correct |
23 |
Correct |
15 ms |
12416 KB |
Output is correct |
24 |
Correct |
14 ms |
12416 KB |
Output is correct |
25 |
Correct |
33 ms |
12540 KB |
Output is correct |
26 |
Correct |
15 ms |
12540 KB |
Output is correct |
27 |
Correct |
14 ms |
12540 KB |
Output is correct |
28 |
Correct |
17 ms |
12540 KB |
Output is correct |
29 |
Correct |
22 ms |
12540 KB |
Output is correct |
30 |
Correct |
26 ms |
12540 KB |
Output is correct |
31 |
Correct |
31 ms |
12540 KB |
Output is correct |
32 |
Correct |
31 ms |
12540 KB |
Output is correct |
33 |
Correct |
27 ms |
12540 KB |
Output is correct |
34 |
Correct |
15 ms |
12540 KB |
Output is correct |
35 |
Correct |
16 ms |
12540 KB |
Output is correct |
36 |
Correct |
16 ms |
12540 KB |
Output is correct |
37 |
Correct |
22 ms |
12540 KB |
Output is correct |
38 |
Correct |
23 ms |
12540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12116 KB |
Output is correct |
2 |
Correct |
11 ms |
12260 KB |
Output is correct |
3 |
Correct |
12 ms |
12260 KB |
Output is correct |
4 |
Correct |
11 ms |
12260 KB |
Output is correct |
5 |
Correct |
11 ms |
12260 KB |
Output is correct |
6 |
Correct |
11 ms |
12260 KB |
Output is correct |
7 |
Correct |
11 ms |
12332 KB |
Output is correct |
8 |
Correct |
12 ms |
12392 KB |
Output is correct |
9 |
Correct |
11 ms |
12392 KB |
Output is correct |
10 |
Correct |
14 ms |
12392 KB |
Output is correct |
11 |
Correct |
14 ms |
12392 KB |
Output is correct |
12 |
Correct |
13 ms |
12392 KB |
Output is correct |
13 |
Correct |
17 ms |
12392 KB |
Output is correct |
14 |
Correct |
14 ms |
12392 KB |
Output is correct |
15 |
Correct |
15 ms |
12392 KB |
Output is correct |
16 |
Correct |
13 ms |
12392 KB |
Output is correct |
17 |
Correct |
15 ms |
12392 KB |
Output is correct |
18 |
Correct |
12 ms |
12392 KB |
Output is correct |
19 |
Execution timed out |
3061 ms |
17200 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12116 KB |
Output is correct |
2 |
Correct |
11 ms |
12260 KB |
Output is correct |
3 |
Correct |
12 ms |
12260 KB |
Output is correct |
4 |
Correct |
11 ms |
12260 KB |
Output is correct |
5 |
Correct |
11 ms |
12260 KB |
Output is correct |
6 |
Correct |
11 ms |
12260 KB |
Output is correct |
7 |
Correct |
11 ms |
12332 KB |
Output is correct |
8 |
Correct |
12 ms |
12392 KB |
Output is correct |
9 |
Correct |
11 ms |
12392 KB |
Output is correct |
10 |
Correct |
14 ms |
12392 KB |
Output is correct |
11 |
Correct |
14 ms |
12392 KB |
Output is correct |
12 |
Correct |
13 ms |
12392 KB |
Output is correct |
13 |
Correct |
17 ms |
12392 KB |
Output is correct |
14 |
Correct |
14 ms |
12392 KB |
Output is correct |
15 |
Correct |
15 ms |
12392 KB |
Output is correct |
16 |
Correct |
13 ms |
12392 KB |
Output is correct |
17 |
Correct |
15 ms |
12392 KB |
Output is correct |
18 |
Correct |
12 ms |
12392 KB |
Output is correct |
19 |
Correct |
12 ms |
12392 KB |
Output is correct |
20 |
Correct |
11 ms |
12392 KB |
Output is correct |
21 |
Correct |
33 ms |
12416 KB |
Output is correct |
22 |
Correct |
13 ms |
12416 KB |
Output is correct |
23 |
Correct |
15 ms |
12416 KB |
Output is correct |
24 |
Correct |
14 ms |
12416 KB |
Output is correct |
25 |
Correct |
33 ms |
12540 KB |
Output is correct |
26 |
Correct |
15 ms |
12540 KB |
Output is correct |
27 |
Correct |
14 ms |
12540 KB |
Output is correct |
28 |
Correct |
17 ms |
12540 KB |
Output is correct |
29 |
Correct |
22 ms |
12540 KB |
Output is correct |
30 |
Correct |
26 ms |
12540 KB |
Output is correct |
31 |
Correct |
31 ms |
12540 KB |
Output is correct |
32 |
Correct |
31 ms |
12540 KB |
Output is correct |
33 |
Correct |
27 ms |
12540 KB |
Output is correct |
34 |
Correct |
15 ms |
12540 KB |
Output is correct |
35 |
Correct |
16 ms |
12540 KB |
Output is correct |
36 |
Correct |
16 ms |
12540 KB |
Output is correct |
37 |
Correct |
22 ms |
12540 KB |
Output is correct |
38 |
Correct |
23 ms |
12540 KB |
Output is correct |
39 |
Execution timed out |
3061 ms |
17200 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |