Submission #115166

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
115166	2019-06-05 14:44:28	songc	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1027 ms	60132 KiB

crocodile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int N, M;
vector<pii> G[101010];
set<pii> U;
int F[101010], S[101010];
bool chk[101010];
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++){
        G[r[i][0]].push_back(pii(r[i][1], l[i]));
        G[r[i][1]].push_back(pii(r[i][0], l[i]));
    }
    for (int i=0; i<k; i++){
        U.insert(pii(0, p[i]));
        chk[p[i]]=true;
    }
    while(!U.empty()){
        int u=U.begin()->second;
        U.erase(U.begin());
        chk[u] = true;
        for (pii v : G[u]){
            if (chk[v.first]) continue;
            if (!F[v.first] || F[v.first] > v.second+S[u]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11