oj.uz

Submission #1030021

# Submission time Handle Problem Language Result Execution time Memory
1030021 2024-07-21T16:19:44 Z Malix Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 487 ms 68896 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
  vector<pii> a(n);
  REP(i,0,m){
    a[R[i][0]].PB({R[i][1],L[i]});
    a[R[i][1]].PB({R[i][0],L[i]});
  }
  vi dist(n,inf);
  vi arr(n,0);
  priority_queue<pi,vector<pi>,greater<pi>> pq;
  REP(i,0,K){
    arr[P[i]]=1;
    dist[P[i]]=0;
    pq.push({0,P[i]});
  }
  while(!pq.empty()){
    int x=pq.top().F;
    int y=pq.top().S;
    pq.pop();
    if(arr[y]>=2)continue;
    arr[y]++;
    if(arr[y]==1)continue;
    dist[y]=x;
    for(auto u:a[y]){
      if(arr[u.F]>=2)continue;
      pq.push({dist[y]+u.S,u.F});
    }
  }
  return dist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4552 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 4 ms 4956 KB Output is correct
13 Correct 5 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4568 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4552 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 4 ms 4956 KB Output is correct
13 Correct 5 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4568 KB Output is correct
16 Correct 417 ms 64916 KB Output is correct
17 Correct 54 ms 15536 KB Output is correct
18 Correct 72 ms 16800 KB Output is correct
19 Correct 487 ms 68896 KB Output is correct
20 Correct 337 ms 57536 KB Output is correct
21 Correct 35 ms 9160 KB Output is correct
22 Correct 306 ms 46512 KB Output is correct