oj.uz

Submission #1086093

# Submission time Handle Problem Language Result Execution time Memory
1086093 2024-09-09T13:43:01 Z MrPavlito Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 597 ms 75952 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>


using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n;

vector<long long> dist(MAXN, inf);
int cnt[MAXN];
vector<vector<pii>> graf(MAXN);
priority_queue<pii, vector<pii>, greater<pii>> pq;

void dikstra()
{
    while(!pq.empty())
    {
        pii it = pq.top();
        pq.pop();
        int u = it.sc;
        int d = it.fi;
        if(dist[u] != inf)continue;
        cnt[u]++;
        if(cnt[u] == 2)
        {
            dist[u] = d;
            for(auto x: graf[u])
            {
                pq.push({d+x.sc, x.fi});
            }
        }
    }
}


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++)
    {
        graf[R[i][0]].pb({R[i][1], L[i]});
        graf[R[i][1]].pb({R[i][0], L[i]});
    }
    for(int i = 0; i<K; i++)
    {
        for(auto x: graf[P[i]])
        {
            pq.push(mp(x.sc, x.fi));
        }
        dist[P[i]] = 0;
    }
    //for(auto x: pq)cout << x.fi << " " << x.sc << endl;
    dikstra();
    return dist[0];
}
/*
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 4 ms 3864 KB Output is correct
10 Correct 2 ms 3636 KB Output is correct
11 Correct 3 ms 3676 KB Output is correct
12 Correct 5 ms 4388 KB Output is correct
13 Correct 5 ms 4444 KB Output is correct
14 Correct 2 ms 3416 KB Output is correct
15 Correct 2 ms 3676 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 4 ms 3864 KB Output is correct
10 Correct 2 ms 3636 KB Output is correct
11 Correct 3 ms 3676 KB Output is correct
12 Correct 5 ms 4388 KB Output is correct
13 Correct 5 ms 4444 KB Output is correct
14 Correct 2 ms 3416 KB Output is correct
15 Correct 2 ms 3676 KB Output is correct
16 Correct 597 ms 71480 KB Output is correct
17 Correct 60 ms 14160 KB Output is correct
18 Correct 71 ms 15700 KB Output is correct
19 Correct 555 ms 75952 KB Output is correct
20 Correct 426 ms 67004 KB Output is correct
21 Correct 28 ms 8276 KB Output is correct
22 Correct 397 ms 47140 KB Output is correct