oj.uz

Submission #92010

# Submission time Handle Problem Language Result Execution time Memory
92010 2019-01-01T02:08:11 Z easrui Race (IOI11_race) C++14
43 / 100
 3000 ms 196744 KB 
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN = 2e5+5;

struct Edge{
    int x,d;
    Edge(){}
    Edge(int a, int b){
        x = a;
        d = b;
    }
};

vector<Edge> T[MN];
Edge A[MN][101];
Edge B[101];

int DFS(int i, int val, int dis, int r, int K){
    if(dis==K) return val;
    if(dis>K) return MN;
    int res = MN;
    for(auto it : T[i]){
        //cout << i << ' ' << it.x << ' ' << r << '\n';
        if(it.x==r) continue;
        res = min(res,DFS(it.x,val+1,dis+it.d,i,K));
    }
    return res;
}

int TDP(int i, int r, int K){
    int res = MN;
    for(auto it : T[i]){
        if(it.x==r) continue;
        res = min(res,TDP(it.x,i,K));
        for(int j=0; j<=K; j++){
            if(j+it.d<=K){
                int l = A[it.x][j].d+1;
                if(l<A[i][j+it.d].d){
                    B[j+it.d] = A[i][j+it.d];
                    A[i][j+it.d] = Edge(it.x,l);
                }
                else if(l<B[j+it.d].d) B[j+it.d] = Edge(it.x,l);
            }
        }
    }
    for(int k=0; k<=K; k++){
        if(A[i][k].x!=A[i][K-k].x) res = min(res,A[i][k].d+A[i][K-k].d);
        else res = min(res,B[k].d+A[i][K-k].d);
        B[k].d = MN;
    }
    return res;
}

int best_path(int N, int K, int H[][2], int L[])
{
    int ans = MN;
    for(int i=0; i<N-1; i++){
        T[H[i][0]].push_back(Edge(H[i][1],L[i]));
        T[H[i][1]].push_back(Edge(H[i][0],L[i]));
    }
    for(int i=0; i<N; i++)
        for(int j=1; j<=K; j++){
            A[i][j].d = MN;
            B[j].d = MN;
        }
    if(K<=100){
        ans = TDP(0,0,K);
    }
    else{
        for(int i=0; i<N; i++){
            ans = min(ans,DFS(i,0,0,i,K));
        }
    }
    if(ans==MN) ans = -1;
    return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 5 ms 5112 KB Output is correct
6 Correct 5 ms 5112 KB Output is correct
7 Correct 5 ms 5112 KB Output is correct
8 Correct 5 ms 5112 KB Output is correct
9 Correct 5 ms 5112 KB Output is correct
10 Correct 5 ms 5112 KB Output is correct
11 Correct 5 ms 5116 KB Output is correct
12 Correct 5 ms 5112 KB Output is correct
13 Correct 5 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 9 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 5 ms 5112 KB Output is correct
18 Correct 5 ms 5112 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 5 ms 5112 KB Output is correct
6 Correct 5 ms 5112 KB Output is correct
7 Correct 5 ms 5112 KB Output is correct
8 Correct 5 ms 5112 KB Output is correct
9 Correct 5 ms 5112 KB Output is correct
10 Correct 5 ms 5112 KB Output is correct
11 Correct 5 ms 5116 KB Output is correct
12 Correct 5 ms 5112 KB Output is correct
13 Correct 5 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 9 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 5 ms 5112 KB Output is correct
18 Correct 5 ms 5112 KB Output is correct
19 Correct 5 ms 4984 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 16 ms 5880 KB Output is correct
22 Correct 2217 ms 13164 KB Output is correct
23 Correct 1788 ms 11896 KB Output is correct
24 Correct 2097 ms 12800 KB Output is correct
25 Correct 2028 ms 12692 KB Output is correct
26 Correct 807 ms 8572 KB Output is correct
27 Correct 1875 ms 12320 KB Output is correct
28 Correct 471 ms 7436 KB Output is correct
29 Correct 757 ms 8568 KB Output is correct
30 Correct 858 ms 8952 KB Output is correct
31 Correct 1524 ms 11128 KB Output is correct
32 Correct 1682 ms 11608 KB Output is correct
33 Correct 1870 ms 12248 KB Output is correct
34 Correct 1280 ms 10488 KB Output is correct
35 Correct 1749 ms 12320 KB Output is correct
36 Correct 1875 ms 13184 KB Output is correct
37 Correct 1612 ms 12152 KB Output is correct
38 Correct 1102 ms 9848 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 5 ms 5112 KB Output is correct
6 Correct 5 ms 5112 KB Output is correct
7 Correct 5 ms 5112 KB Output is correct
8 Correct 5 ms 5112 KB Output is correct
9 Correct 5 ms 5112 KB Output is correct
10 Correct 5 ms 5112 KB Output is correct
11 Correct 5 ms 5116 KB Output is correct
12 Correct 5 ms 5112 KB Output is correct
13 Correct 5 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 9 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 5 ms 5112 KB Output is correct
18 Correct 5 ms 5112 KB Output is correct
19 Correct 218 ms 90084 KB Output is correct
20 Correct 234 ms 90016 KB Output is correct
21 Correct 215 ms 89980 KB Output is correct
22 Correct 246 ms 89848 KB Output is correct
23 Correct 179 ms 90184 KB Output is correct
24 Correct 185 ms 89948 KB Output is correct
25 Correct 262 ms 95380 KB Output is correct
26 Correct 140 ms 100600 KB Output is correct
27 Correct 354 ms 175152 KB Output is correct
28 Correct 454 ms 196744 KB Output is correct
29 Correct 441 ms 195320 KB Output is correct
30 Correct 394 ms 175096 KB Output is correct
31 Correct 441 ms 175096 KB Output is correct
32 Correct 520 ms 174968 KB Output is correct
33 Correct 517 ms 174328 KB Output is correct
34 Correct 478 ms 174656 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5116 KB Output is correct
5 Correct 5 ms 5112 KB Output is correct
6 Correct 5 ms 5112 KB Output is correct
7 Correct 5 ms 5112 KB Output is correct
8 Correct 5 ms 5112 KB Output is correct
9 Correct 5 ms 5112 KB Output is correct
10 Correct 5 ms 5112 KB Output is correct
11 Correct 5 ms 5116 KB Output is correct
12 Correct 5 ms 5112 KB Output is correct
13 Correct 5 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 9 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 5 ms 5112 KB Output is correct
18 Correct 5 ms 5112 KB Output is correct
19 Correct 5 ms 4984 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 16 ms 5880 KB Output is correct
22 Correct 2217 ms 13164 KB Output is correct
23 Correct 1788 ms 11896 KB Output is correct
24 Correct 2097 ms 12800 KB Output is correct
25 Correct 2028 ms 12692 KB Output is correct
26 Correct 807 ms 8572 KB Output is correct
27 Correct 1875 ms 12320 KB Output is correct
28 Correct 471 ms 7436 KB Output is correct
29 Correct 757 ms 8568 KB Output is correct
30 Correct 858 ms 8952 KB Output is correct
31 Correct 1524 ms 11128 KB Output is correct
32 Correct 1682 ms 11608 KB Output is correct
33 Correct 1870 ms 12248 KB Output is correct
34 Correct 1280 ms 10488 KB Output is correct
35 Correct 1749 ms 12320 KB Output is correct
36 Correct 1875 ms 13184 KB Output is correct
37 Correct 1612 ms 12152 KB Output is correct
38 Correct 1102 ms 9848 KB Output is correct
39 Correct 218 ms 90084 KB Output is correct
40 Correct 234 ms 90016 KB Output is correct
41 Correct 215 ms 89980 KB Output is correct
42 Correct 246 ms 89848 KB Output is correct
43 Correct 179 ms 90184 KB Output is correct
44 Correct 185 ms 89948 KB Output is correct
45 Correct 262 ms 95380 KB Output is correct
46 Correct 140 ms 100600 KB Output is correct
47 Correct 354 ms 175152 KB Output is correct
48 Correct 454 ms 196744 KB Output is correct
49 Correct 441 ms 195320 KB Output is correct
50 Correct 394 ms 175096 KB Output is correct
51 Correct 441 ms 175096 KB Output is correct
52 Correct 520 ms 174968 KB Output is correct
53 Correct 517 ms 174328 KB Output is correct
54 Correct 478 ms 174656 KB Output is correct
55 Correct 368 ms 13604 KB Output is correct
56 Execution timed out 3048 ms 13560 KB Time limit exceeded
57 Halted 0 ms 0 KB -