oj.uz

Submission #824268

# Submission time Handle Problem Language Result Execution time Memory
824268 2023-08-13T22:31:45 Z trangtranha28 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 363 ms 46968 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <climits>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

const int MAXN = 1e5 + 2;

int n, m;
int dis[MAXN] = {0}, dis2[MAXN] = {0};
bool check[MAXN] = {0};

vector <int> exits;
vector <pair <int, int> > adj[MAXN];

int Dijkstra() {
	// reset:
	memset(dis, 63, sizeof(dis));
	memset(dis2, 63, sizeof(dis2));
	
	// main:
	priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
	
	for(int i = 0; i < (int)(exits.size()); i++) {
    	dis[exits[i]] = 0;
		dis2[exits[i]] = 0;
		pq.push(make_pair(0, exits[i]));
	}
	
    while(pq.empty() == false) {
        int u = pq.top().second;
        pq.pop();
		
        if(check[u] == true) {
        	continue;
		}
		check[u] = true;
		
        for(int i = 0; i < (int)(adj[u].size()); i++) {
            int v = adj[u][i].first, w = adj[u][i].second;
            if(dis[v] > dis2[u] + w) {
                dis2[v] = dis[v];
				dis[v] = dis2[u] + w;
                pq.push(make_pair(dis2[v], v));
            } else if(dis2[v] > dis2[u] + w) {
            	dis2[v] = dis2[u] + w;
				pq.push(make_pair(dis2[v], v));
			}
        }
    }
    return dis2[0];
}

int travel_plan(int N, int M, int R[][2], int L[], int k, int p[]) {
    n = N, m = M;
    for(int i = 0; i < m; i++) {
        int a = R[i][0], b = R[i][1], c = L[i];
        adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
    }
    for(int i = 0; i < k; i++) {
    	exits.push_back(p[i]);
	}
    return Dijkstra();
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 1 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 4 ms 3796 KB Output is correct
13 Correct 4 ms 3796 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 1 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 4 ms 3796 KB Output is correct
13 Correct 4 ms 3796 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct
16 Correct 300 ms 42812 KB Output is correct
17 Correct 68 ms 11616 KB Output is correct
18 Correct 81 ms 13040 KB Output is correct
19 Correct 363 ms 46968 KB Output is correct
20 Correct 225 ms 37416 KB Output is correct
21 Correct 32 ms 7232 KB Output is correct
22 Correct 240 ms 32756 KB Output is correct