oj.uz

Submission #497261

# Submission time Handle Problem Language Result Execution time Memory
497261 2021-12-22T21:47:25 Z Skywk Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 669 ms 84580 KB 
#include "crocodile.h"
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<queue>
#include<stack>
#define lmt 100000
#define LMT 1000000
#define mod 1000000007
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
 
using namespace std;

vector<pil> graph[lmt];
long long best[LMT];
bool once[LMT];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for(int i=0; i<m;  i++)
    {
        int a=R[i][0], b=R[i][1];
        graph[a].push_back({b, L[i]});
        graph[b].push_back({a, L[i]});
    }
    
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for(int i=0, x; i<k; i++)
        pq.push({0, P[i]});

    for(int i=0; i<n; i++)
        best[i]=-1;
    while(!pq.empty())
    {
        auto p=pq.top();
        pq.pop();
        int x=p.second; long long w=p.first;

        if(best[x] != -1)
            continue;
        if(w!=0 && !once[x])
        {
            once[x]=true;
            continue;
        }

        best[x]=w;
        for(auto y : graph[x])
        {
            if(best[y.first] != -1)
                continue;
            pq.push({w+y.second, y.first});
        }
    }
    return best[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:37:18: warning: unused variable 'x' [-Wunused-variable]
   37 |     for(int i=0, x; i<k; i++)
      |                  ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2604 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2756 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 1 ms 2764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2604 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2756 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 1 ms 2764 KB Output is correct
9 Correct 3 ms 3220 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 5 ms 3660 KB Output is correct
13 Correct 5 ms 3788 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2604 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2756 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 1 ms 2764 KB Output is correct
9 Correct 3 ms 3220 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 5 ms 3660 KB Output is correct
13 Correct 5 ms 3788 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 632 ms 80992 KB Output is correct
17 Correct 71 ms 13772 KB Output is correct
18 Correct 90 ms 16056 KB Output is correct
19 Correct 669 ms 84580 KB Output is correct
20 Correct 418 ms 71640 KB Output is correct
21 Correct 51 ms 8156 KB Output is correct
22 Correct 378 ms 50300 KB Output is correct