oj.uz

Submission #1093773

# Submission time Handle Problem Language Result Execution time Memory
1093773 2024-09-27T11:43:05 Z Aviansh Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1666 ms 139696 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
 
using namespace std;
 
int travel_plan(int n, int m, int edges[][2], int w[], int k, int p[])
{
    set<pair<int,int>> g[n];
    for(int i =0;i<m;i++){
        g[edges[i][0]].insert({edges[i][1],w[i]});
        g[edges[i][1]].insert({edges[i][0],w[i]});
    }
    bool ex[n];
    bool rem[n];
    bool vis[n];
    fill(rem,rem+n,0);
    fill(ex,ex+n,0);
    fill(vis,vis+n,0);
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>pq; // dist,destination,origin
    for(int i = 0;i<k;i++){
        vis[p[i]]=1;
        ex[p[i]]=1;
        for(pair<int,int>pa : g[p[i]]){
            pq.push({pa.second,pa.first,p[i]});
        }
    }
    while(!pq.empty()){
        array<int,3> a = pq.top();
        pq.pop();
        if(vis[a[1]]){
            continue;
        }
        if(rem[a[1]]){
          	if(a[1]==0)
            	return a[0];
            for(pair<int,int>p:g[a[1]]){
                if(vis[p.first]) continue;
                pq.push({a[0]+p.second,p.first,a[1]});
            }
            vis[a[1]]=1;
        }
        else{
            //cout << "removing edge: " << a[1] << " " << a[2] << "\n";
            rem[a[1]]=1;
        }
    }
  	return -1;
    fill(vis,vis+n,0);
    pq.push({0,0,-1});
    vis[0]=1;
    while(!pq.empty()){
        array<int,3>a=pq.top();
        pq.pop();
        vis[a[1]]=1;
        if(ex[a[1]]) return a[0];
        for(pair<int,int>p:g[a[1]]){
            if(vis[p.first]) continue;
            pq.push({p.second+a[0],p.first,a[1]});
        }
    }
    assert(0);
    return -1;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 6 ms 1720 KB Output is correct
13 Correct 4 ms 1372 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 604 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 6 ms 1720 KB Output is correct
13 Correct 4 ms 1372 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1666 ms 135300 KB Output is correct
17 Correct 65 ms 29704 KB Output is correct
18 Correct 72 ms 30808 KB Output is correct
19 Correct 1294 ms 139696 KB Output is correct
20 Correct 438 ms 119120 KB Output is correct
21 Correct 33 ms 12884 KB Output is correct
22 Correct 620 ms 111512 KB Output is correct