oj.uz

Submission #745295

# Submission time Handle Problem Language Result Execution time Memory
745295 2023-05-19T19:02:08 Z CSQ31 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 487 ms 61448 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll A,ll B) {if(!B)return A;return gcd(B,A%B);}
const int INF = 1e9+2,MAXN = 1e5+5;
int dist[MAXN],mn0[MAXN],mn1[MAXN];
vector<pii> adj[MAXN];
void upd(int i,int x){
	if(x <= mn0[i]){
		mn1[i] = mn0[i];
		mn0[i] = x;
	}else if(x < mn1[i]){
		mn1[i] = x;
	}
	
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<N;i++)mn0[i] = mn1[i] = dist[i] = INF;
	for(int i=0;i<M;i++){
		adj[R[i][0]].pb({R[i][1],L[i]});
		adj[R[i][1]].pb({R[i][0],L[i]});
	}
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=0;i<K;i++){
		dist[P[i]] = 0;
		pq.push({0,P[i]});
	}
	while(!pq.empty()){
		int v = pq.top().se;
		int d = pq.top().fi;
		pq.pop();
		if(d != dist[v])continue;
		for(auto x:adj[v]){
			int w = x.se;
			int u = x.fi;
			upd(u,d+w);
			if(mn1[u]< dist[u]){
				dist[u] =  mn1[u];
				pq.push({dist[u],u});
			}			
		}
	}
	return dist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 4 ms 3028 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 4 ms 3028 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 395 ms 41284 KB Output is correct
17 Correct 71 ms 14028 KB Output is correct
18 Correct 88 ms 15512 KB Output is correct
19 Correct 487 ms 61448 KB Output is correct
20 Correct 265 ms 49528 KB Output is correct
21 Correct 34 ms 7756 KB Output is correct
22 Correct 281 ms 46200 KB Output is correct