oj.uz

Submission #725308

# Submission time Handle Problem Language Result Execution time Memory
725308 2023-04-17T08:22:36 Z onepunchac168 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 415 ms 66000 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair <int,int> ii;
typedef pair <int ,ii> iii;
const char nl='\n';
ii dp[100005][2];
vector <int > gg;
vector <ii> vt[100005];
int n;
int dijkstra()
{
    for (int i=0;i<n;i++)
    {
        dp[i][0]=dp[i][1]={1e9+5,-1};
    }
    priority_queue<iii,vector <iii> ,greater <iii> > qu;
    for (auto v:gg)
    {
        dp[v][0]=dp[v][1]={0,-1};
        qu.push({0,{v,1}});
    }
    while (!qu.empty())
    {
        int aa=qu.top().fi;
        int u=qu.top().se.fi;
        int pos=qu.top().se.se;
        qu.pop();
        if (u==0&&pos==1)
        {
            return aa;
        }
        if (aa!=dp[u][pos].fi){continue;}
        for (auto v:vt[u])
        {
            if (dp[v.fi][0].fi>dp[u][pos].fi+v.se)
            {
                dp[v.fi][1]=dp[v.fi][0];
                dp[v.fi][0]={dp[u][pos].fi+v.se,u};
                qu.push({dp[v.fi][1].fi,{v.fi,1}});
            }
            else if (dp[v.fi][1].fi>dp[u][pos].fi+v.se)
            {
                dp[v.fi][1]={dp[u][pos].fi+v.se,u};
                qu.push({dp[v.fi][1].fi,{v.fi,1}});
            }
        }

    }

}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N;
    for (int i=0;i<M;i++)
    {
        int aa=R[i][0];
        int bb=R[i][1];
        int cc=L[i];
        vt[aa].pb({bb,cc});
        vt[bb].pb({aa,cc});
    }
    for (int i=0;i<K;i++)
    {
        gg.pb(P[i]);
    }
    return dijkstra();

}

Compilation message

crocodile.cpp: In function 'int dijkstra()':
crocodile.cpp:22:54: warning: control reaches end of non-void function [-Wreturn-type]
   22 |     priority_queue<iii,vector <iii> ,greater <iii> > qu;
      |                                                      ^~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2788 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2672 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2788 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2672 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 3 ms 2664 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 5 ms 3180 KB Output is correct
13 Correct 5 ms 3224 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2788 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2672 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 3 ms 2664 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 5 ms 3180 KB Output is correct
13 Correct 5 ms 3224 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 351 ms 59584 KB Output is correct
17 Correct 83 ms 16204 KB Output is correct
18 Correct 77 ms 16848 KB Output is correct
19 Correct 415 ms 66000 KB Output is correct
20 Correct 235 ms 49572 KB Output is correct
21 Correct 41 ms 8432 KB Output is correct
22 Incorrect 274 ms 46788 KB Output isn't correct
23 Halted 0 ms 0 KB -