oj.uz

Submission #92007

# Submission time Handle Problem Language Result Execution time Memory
92007 2019-01-01T00:39:12 Z easrui Race (IOI11_race) C++14
0 / 100
 260 ms 5064 KB 
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN = 2e5+5;

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

vector<Edge> T[MN];

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]){
        if(it.x==r) continue;
        res = min(res,DFS(it.x,val+1,dis+it.d,i,K));
    }
    return res;
}

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4984 KB Output is correct
2 Correct 6 ms 5064 KB Output is correct
3 Incorrect 5 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4984 KB Output is correct
2 Correct 6 ms 5064 KB Output is correct
3 Incorrect 5 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4984 KB Output is correct
2 Correct 6 ms 5064 KB Output is correct
3 Incorrect 5 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4984 KB Output is correct
2 Correct 6 ms 5064 KB Output is correct
3 Incorrect 5 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -