oj.uz

Submission #940562

# Submission time Handle Problem Language Result Execution time Memory
940562 2024-03-07T10:42:11 Z groshi Wild Boar (JOI18_wild_boar) C++17
47 / 100
 10505 ms 1048576 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int mam[100100];
struct wi{
    vector<int> Q;
    int dp[100100][2][2];///koszt, od kogo
}*w;
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,t,l,x,y,z;
    cin>>n>>m>>t>>l;
    w=new wi[n+3];
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        w[x].Q.push_back(y);
        w[x].Q.push_back(z);
        w[y].Q.push_back(x);
        w[y].Q.push_back(z);
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=l;j++)
            w[i].dp[j][0][0]=1e18,w[i].dp[j][0][1]=1e18;
    for(int i=1;i<=l;i++)
        cin>>mam[i];
    cin>>x>>y;
    mam[x]=y;
    priority_queue<pair<pair<int,int>,pair<int,int> > > kolejka;
    kolejka.push({{0,mam[1]},{0,0}});
    while(!kolejka.empty())
    {
        auto para=kolejka.top();
        kolejka.pop();
        int x=para.first.second;
        int koszt=-para.first.first;
        int gdzie=para.second.first;
        int skad=para.second.second;
        if(mam[gdzie+1]==x)
            gdzie++;
        if(w[x].dp[gdzie][0][1]<=koszt)
            continue;
        if(w[x].dp[gdzie][0][0]>koszt)
        {
            w[x].dp[gdzie][0][0]=koszt;
            w[x].dp[gdzie][1][0]=skad;
        }
        else if(w[x].dp[gdzie][0][1]>koszt)
        {
            if(skad==w[x].dp[gdzie][1][0])
                continue;
            w[x].dp[gdzie][0][1]=koszt;
            w[x].dp[gdzie][1][1]=skad;
        }
        for(int i=0;i<w[x].Q.size();i+=2)
        {
            int pom=w[x].Q[i];
            int ile=w[x].Q[i+1];
            if(pom==skad)
                continue;
            kolejka.push({{-koszt-ile,pom},{gdzie,x}});
        }
    }
    if(w[mam[l]].dp[l][0][0]==1000000000000000000)
        cout<<"-1";
    else cout<<w[mam[l]].dp[l][0][0];
    return 0;
}

Compilation message

wild_boar.cpp: In function 'int32_t main()':
wild_boar.cpp:58:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int i=0;i<w[x].Q.size();i+=2)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 19032 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 3 ms 20828 KB Output is correct
13 Correct 2 ms 20968 KB Output is correct
14 Correct 3 ms 20828 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 3 ms 22876 KB Output is correct
17 Correct 3 ms 23052 KB Output is correct
18 Correct 3 ms 23000 KB Output is correct
19 Correct 3 ms 24924 KB Output is correct
20 Correct 3 ms 24924 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 2 ms 14684 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 2 ms 14680 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 19032 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 3 ms 20828 KB Output is correct
13 Correct 2 ms 20968 KB Output is correct
14 Correct 3 ms 20828 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 3 ms 22876 KB Output is correct
17 Correct 3 ms 23052 KB Output is correct
18 Correct 3 ms 23000 KB Output is correct
19 Correct 3 ms 24924 KB Output is correct
20 Correct 3 ms 24924 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 2 ms 14684 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 2 ms 14680 KB Output is correct
26 Correct 12 ms 45404 KB Output is correct
27 Correct 149 ms 315668 KB Output is correct
28 Correct 103 ms 316180 KB Output is correct
29 Correct 9295 ms 315228 KB Output is correct
30 Correct 9762 ms 315204 KB Output is correct
31 Correct 9810 ms 316752 KB Output is correct
32 Correct 10505 ms 316916 KB Output is correct
33 Correct 8578 ms 473820 KB Output is correct
34 Correct 8629 ms 473884 KB Output is correct
35 Correct 8845 ms 472224 KB Output is correct
36 Correct 8973 ms 472164 KB Output is correct
37 Correct 8876 ms 473504 KB Output is correct
38 Correct 7784 ms 630500 KB Output is correct
39 Correct 7774 ms 629624 KB Output is correct
40 Correct 7802 ms 630216 KB Output is correct
41 Correct 7725 ms 630612 KB Output is correct
42 Correct 6808 ms 723820 KB Output is correct
43 Correct 6288 ms 786468 KB Output is correct
44 Correct 6348 ms 786376 KB Output is correct
45 Correct 1878 ms 943552 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 19032 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 3 ms 20828 KB Output is correct
13 Correct 2 ms 20968 KB Output is correct
14 Correct 3 ms 20828 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 3 ms 22876 KB Output is correct
17 Correct 3 ms 23052 KB Output is correct
18 Correct 3 ms 23000 KB Output is correct
19 Correct 3 ms 24924 KB Output is correct
20 Correct 3 ms 24924 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 2 ms 14684 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 2 ms 14680 KB Output is correct
26 Correct 12 ms 45404 KB Output is correct
27 Correct 149 ms 315668 KB Output is correct
28 Correct 103 ms 316180 KB Output is correct
29 Correct 9295 ms 315228 KB Output is correct
30 Correct 9762 ms 315204 KB Output is correct
31 Correct 9810 ms 316752 KB Output is correct
32 Correct 10505 ms 316916 KB Output is correct
33 Correct 8578 ms 473820 KB Output is correct
34 Correct 8629 ms 473884 KB Output is correct
35 Correct 8845 ms 472224 KB Output is correct
36 Correct 8973 ms 472164 KB Output is correct
37 Correct 8876 ms 473504 KB Output is correct
38 Correct 7784 ms 630500 KB Output is correct
39 Correct 7774 ms 629624 KB Output is correct
40 Correct 7802 ms 630216 KB Output is correct
41 Correct 7725 ms 630612 KB Output is correct
42 Correct 6808 ms 723820 KB Output is correct
43 Correct 6288 ms 786468 KB Output is correct
44 Correct 6348 ms 786376 KB Output is correct
45 Correct 1878 ms 943552 KB Output is correct
46 Correct 39 ms 247632 KB Output is correct
47 Runtime error 579 ms 1048576 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 19032 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 3 ms 20828 KB Output is correct
13 Correct 2 ms 20968 KB Output is correct
14 Correct 3 ms 20828 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 3 ms 22876 KB Output is correct
17 Correct 3 ms 23052 KB Output is correct
18 Correct 3 ms 23000 KB Output is correct
19 Correct 3 ms 24924 KB Output is correct
20 Correct 3 ms 24924 KB Output is correct
21 Correct 2 ms 14684 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 2 ms 14684 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 2 ms 14680 KB Output is correct
26 Correct 12 ms 45404 KB Output is correct
27 Correct 149 ms 315668 KB Output is correct
28 Correct 103 ms 316180 KB Output is correct
29 Correct 9295 ms 315228 KB Output is correct
30 Correct 9762 ms 315204 KB Output is correct
31 Correct 9810 ms 316752 KB Output is correct
32 Correct 10505 ms 316916 KB Output is correct
33 Correct 8578 ms 473820 KB Output is correct
34 Correct 8629 ms 473884 KB Output is correct
35 Correct 8845 ms 472224 KB Output is correct
36 Correct 8973 ms 472164 KB Output is correct
37 Correct 8876 ms 473504 KB Output is correct
38 Correct 7784 ms 630500 KB Output is correct
39 Correct 7774 ms 629624 KB Output is correct
40 Correct 7802 ms 630216 KB Output is correct
41 Correct 7725 ms 630612 KB Output is correct
42 Correct 6808 ms 723820 KB Output is correct
43 Correct 6288 ms 786468 KB Output is correct
44 Correct 6348 ms 786376 KB Output is correct
45 Correct 1878 ms 943552 KB Output is correct
46 Correct 39 ms 247632 KB Output is correct
47 Runtime error 579 ms 1048576 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -