oj.uz

Submission #483924

# Submission time Handle Problem Language Result Execution time Memory
483924 2021-11-01T11:50:29 Z PoPularPlusPlus Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 501 ms 44736 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
 
vector<pair<int,int>	> adj[100002];
int dp[100002],dp1[100002];

void dijkstra(int p[], int k) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
   for(int i = 0; i < k; i++){
	   q.push({0,p[i]});
	   dp[p[i]] = dp1[p[i]] = 0;
   }
    while (not q.empty()) {
      const auto [d, x] = q.top();
      q.pop();
      if (dp1[x] < d) continue;
      for (const auto &[y, w] : adj[x]) {
        int cur = d + w;
        if (cur < dp[y]) {
          swap(dp[y], cur);
        }
        if (cur < dp1[y]) {
          dp1[y] = cur;
          q.push(make_pair(dp1[y], y));
        }
      }
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	for(int i = 0; i < m; i++){
		adj[r[i][0]].pb(mp(r[i][1] , l[i]));
		adj[r[i][1]].pb(mp(r[i][0] , l[i]));
	}
	for(int i = 0; i < n; i++)dp[i] = dp1[i] = INT_MAX;
	dijkstra(p,k);
	/*for(int i = 0; i < n; i++){
		cout << dp[i] << ' ' << dp1[i] << '\n';
	}*/
	return dp1[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 4 ms 3020 KB Output is correct
13 Correct 4 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 389 ms 41068 KB Output is correct
17 Correct 64 ms 10436 KB Output is correct
18 Correct 81 ms 11780 KB Output is correct
19 Correct 501 ms 44736 KB Output is correct
20 Correct 266 ms 36580 KB Output is correct
21 Correct 31 ms 6148 KB Output is correct
22 Correct 255 ms 31816 KB Output is correct