oj.uz

Submission #308829

# Submission time Handle Problem Language Result Execution time Memory
308829 2020-10-02T04:36:53 Z juggernaut Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1024 ms 75384 KB 
#include"crocodile.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
vector<pair<ll,ll>>g[100005];
pair<ll,ll>a[100005];
ll inf=2e9;
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
    for(int i=0;i<n;i++)a[i]={inf,inf};
    set<pair<ll,ll>>q;
    for(int i=0;i<m;i++){
        g[r[i][0]].push_back({r[i][1],l[i]});
        g[r[i][1]].push_back({r[i][0],l[i]});
    }
    for(int i=0;i<k;i++)
        q.insert({0,p[i]}),a[p[i]]={0,0};
    while(!q.empty()){
        ll len=q.begin()->fr;
        ll v=q.begin()->sc;
        q.erase(q.begin());
        if(len>a[v].sc)continue;
        for(auto to:g[v])
            if(a[to.fr].sc>len+to.sc){
                a[to.fr].sc=len+to.sc;
                if(a[to.fr].fr>a[to.fr].sc)swap(a[to.fr].fr,a[to.fr].sc);
                if(a[to.fr].sc<inf)q.insert({a[to.fr].sc,to.fr});
            }
    }
    return a[0].sc;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3212 KB Output is correct
13 Correct 6 ms 3416 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3212 KB Output is correct
13 Correct 6 ms 3416 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 720 ms 67400 KB Output is correct
17 Correct 94 ms 14456 KB Output is correct
18 Correct 130 ms 16632 KB Output is correct
19 Correct 1024 ms 75384 KB Output is correct
20 Correct 338 ms 54648 KB Output is correct
21 Correct 52 ms 8440 KB Output is correct
22 Correct 377 ms 50044 KB Output is correct