oj.uz

Submission #1100322

# Submission time Handle Problem Language Result Execution time Memory
1100322 2024-10-13T13:44:41 Z vjudge1 Race (IOI11_race) C++17
21 / 100
 23 ms 14672 KB 
#include <iostream>
#include <vector>
#include <array>
using namespace std;
int k,dp[200000];
vector<pair<int,int>>v[200000];
int dfs(int x,int s)
{
    if(s>k||dp[x])return -1;
    else if(s==k)return 0;
    int sm=-1;
    dp[x]=1;
    for(auto [i,vl]:v[x])
    {
        int sl=dfs(i,s+vl);
        if(sl!=-1)
        {
            if(sm==-1)sm=sl+1;
            else
            {
                sm=min(sl+1,sm);
            }
        }
    }
    dp[x]=0;
    return sm;
}
int best_path(int n, int K, int h[][2], int l[])
{
    k=K;
    for(int x=0;x<n-1;x++)
    {
        v[h[x][0]].push_back({h[x][1],l[x]});
        v[h[x][1]].push_back({h[x][0],l[x]});
    }
    if(n<=1000)
    {
        int ans=-1;
        for(int x=0;x<n;x++)
        {
            int s=dfs(x,0);
            if(s!=-1)
            {
                if(ans==-1)ans=s;
                else
                {
                    ans=min(ans,s);
                }
            }
        }
        return ans;
    }
    else
    {
        return 0;
    }
}
/*int main()
{
    int n,k;
    cin>>n>>k;
    int h[n][2],l[n];
    for(int x=0;x<n-1;x++)
    {
        cin>>h[x][0]>>h[x][1]>>l[x];
    }
    cout<<best_path(n,k,h,l);
}*/

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 8784 KB Output is correct
9 Correct 3 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 2 ms 8784 KB Output is correct
12 Correct 2 ms 8636 KB Output is correct
13 Correct 2 ms 8632 KB Output is correct
14 Correct 2 ms 8784 KB Output is correct
15 Correct 2 ms 8784 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Correct 2 ms 8784 KB Output is correct
20 Correct 2 ms 8784 KB Output is correct
21 Correct 9 ms 8624 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8784 KB Output is correct
24 Correct 2 ms 8784 KB Output is correct
25 Correct 10 ms 8784 KB Output is correct
26 Correct 2 ms 8784 KB Output is correct
27 Correct 2 ms 8952 KB Output is correct
28 Correct 5 ms 8628 KB Output is correct
29 Correct 7 ms 8784 KB Output is correct
30 Correct 8 ms 8784 KB Output is correct
31 Correct 10 ms 8952 KB Output is correct
32 Correct 13 ms 8784 KB Output is correct
33 Correct 9 ms 8784 KB Output is correct
34 Correct 2 ms 8784 KB Output is correct
35 Correct 3 ms 8784 KB Output is correct
36 Correct 2 ms 8784 KB Output is correct
37 Correct 7 ms 8992 KB Output is correct
38 Correct 9 ms 8808 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 8784 KB Output is correct
9 Correct 3 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 2 ms 8784 KB Output is correct
12 Correct 2 ms 8636 KB Output is correct
13 Correct 2 ms 8632 KB Output is correct
14 Correct 2 ms 8784 KB Output is correct
15 Correct 2 ms 8784 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Incorrect 23 ms 14672 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 8784 KB Output is correct
9 Correct 3 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 2 ms 8784 KB Output is correct
12 Correct 2 ms 8636 KB Output is correct
13 Correct 2 ms 8632 KB Output is correct
14 Correct 2 ms 8784 KB Output is correct
15 Correct 2 ms 8784 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Correct 2 ms 8784 KB Output is correct
20 Correct 2 ms 8784 KB Output is correct
21 Correct 9 ms 8624 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8784 KB Output is correct
24 Correct 2 ms 8784 KB Output is correct
25 Correct 10 ms 8784 KB Output is correct
26 Correct 2 ms 8784 KB Output is correct
27 Correct 2 ms 8952 KB Output is correct
28 Correct 5 ms 8628 KB Output is correct
29 Correct 7 ms 8784 KB Output is correct
30 Correct 8 ms 8784 KB Output is correct
31 Correct 10 ms 8952 KB Output is correct
32 Correct 13 ms 8784 KB Output is correct
33 Correct 9 ms 8784 KB Output is correct
34 Correct 2 ms 8784 KB Output is correct
35 Correct 3 ms 8784 KB Output is correct
36 Correct 2 ms 8784 KB Output is correct
37 Correct 7 ms 8992 KB Output is correct
38 Correct 9 ms 8808 KB Output is correct
39 Incorrect 23 ms 14672 KB Output isn't correct
40 Halted 0 ms 0 KB -