oj.uz

Submission #237248

# Submission time Handle Problem Language Result Execution time Memory
237248 2020-06-05T12:43:38 Z Autoratch Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 760 ms 63848 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int> 

const int N = 1e5 + 1;

vector<pair<int,int> > adj[N];
vector<int> ep;
bool epp[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
int dist[N],dis1[N],dis2[N];
bool visited[N];

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
    for(int i = 0;i < m;i++)
    {
        int a = r[i][0],b = r[i][1],d = l[i];
        adj[a].push_back({d,b});
        adj[b].push_back({d,a});
    }
    for(int i = 0;i < k;i++) ep.push_back(p[i]);
    for(int i = 0;i < n;i++) dist[i] = dis1[i] = dis2[i] = INT_MAX;
    for(int x : ep) dist[x] = dis1[x] = dis2[x] = 0,q.push({0,x}),epp[x] = true;
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
    }
    for(int i = 0;i < n;i++) visited[i] = false;
    for(int x : ep) q.push({0,x});
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        if(dis2[u]==INT_MAX) continue;
        for(auto [d,v] : adj[u])
        {
            if(dis2[u]+d<dis1[v]) dis2[v] = dis1[v],dis1[v] = dis2[u]+d,q.push({dis2[v],v});
            else if(dis2[u]+d<dis2[v]) dis2[v] = dis2[u]+d,q.push({dis2[v],v});
        }
    }
    return dis2[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:32:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [d,v] : adj[u]) if(dist[u]+d<dist[v]) dist[v] = dist[u]+d,q.push({dist[v],v});
                  ^
crocodile.cpp:43:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [d,v] : adj[u])
                  ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 10 ms 3000 KB Output is correct
10 Correct 7 ms 2688 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 10 ms 3200 KB Output is correct
13 Correct 10 ms 3200 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 7 ms 2816 KB Output is correct
16 Correct 567 ms 58340 KB Output is correct
17 Correct 121 ms 15476 KB Output is correct
18 Correct 182 ms 16920 KB Output is correct
19 Correct 760 ms 63848 KB Output is correct
20 Correct 347 ms 49656 KB Output is correct
21 Correct 61 ms 8312 KB Output is correct
22 Correct 396 ms 46584 KB Output is correct