oj.uz

Submission #546913

# Submission time Handle Problem Language Result Execution time Memory
546913 2022-04-08T20:37:20 Z ala2 Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 28400 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;
vector<pair<int,int>>v[100100];
const int inf=1e18;
int dp[100][100][1000];
int f(int x,int y,int k)
{
    if(k<0)
      return inf;
    if(x==y)
    {
        return 0;
    }
    if(dp[x][y][k])
        return dp[x][y][k];
    int mn=1e18;
    for(int i=0;i<v[x].size();i++)
    {
        mn=min(mn,v[x][i].second+f(v[x][i].first,y,k-1));
    }
    return dp[x][y][k]=mn;

}
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int c,o,w;
        cin>>c>>o>>w;
        v[c].pb({o,w});
    }
    int q,k;
    cin>>k>>q;
    k=min(k,n*n*2);
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(f(x,y,k)<=1e15)
        cout<<f(x,y,k)<<endl;
        else cout<<-1<<endl;
    }

}

Compilation message

Main.cpp: In function 'long long int f(long long int, long long int, long long int)':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<v[x].size();i++)
      |                 ~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21992 KB Output is correct
2 Correct 21 ms 22056 KB Output is correct
3 Correct 24 ms 22096 KB Output is correct
4 Correct 21 ms 22028 KB Output is correct
5 Correct 24 ms 21996 KB Output is correct
6 Correct 29 ms 22264 KB Output is correct
7 Correct 33 ms 22216 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 29 ms 23028 KB Output is correct
8 Correct 45 ms 24472 KB Output is correct
9 Correct 24 ms 22028 KB Output is correct
10 Correct 42 ms 23304 KB Output is correct
11 Correct 48 ms 22524 KB Output is correct
12 Correct 113 ms 23628 KB Output is correct
13 Execution timed out 1085 ms 28400 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 21 ms 21992 KB Output is correct
8 Correct 21 ms 22056 KB Output is correct
9 Correct 24 ms 22096 KB Output is correct
10 Correct 21 ms 22028 KB Output is correct
11 Correct 24 ms 21996 KB Output is correct
12 Correct 29 ms 22264 KB Output is correct
13 Correct 33 ms 22216 KB Output is correct
14 Correct 29 ms 23028 KB Output is correct
15 Correct 45 ms 24472 KB Output is correct
16 Correct 24 ms 22028 KB Output is correct
17 Correct 42 ms 23304 KB Output is correct
18 Correct 48 ms 22524 KB Output is correct
19 Correct 113 ms 23628 KB Output is correct
20 Execution timed out 1085 ms 28400 KB Time limit exceeded
21 Halted 0 ms 0 KB -