oj.uz

Submission #676414

# Submission time Handle Problem Language Result Execution time Memory
676414 2022-12-30T20:30:10 Z bane Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 507 ms 87424 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>
#include <climits>
#include <list>
using namespace std;
      
using ll = long long;
using db = long double; // or double, if TL is tight
using llu = unsigned long long;
using str = string; // yay python! 
      
// pairs
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdb = pair<db,db>;
#define mp make_pair
#define fr first
#define sc second
      
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pll>;
using vpd = V<pdb>;
#define ms0(x) memset(x , 0, sizeof(x))
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
      
#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
      
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
      
const int MOD = (int)1e9+7; // 998244353;
const int MX = (int)2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
  
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	priority_queue<pair<ll,int>>q;
	vector<pair<int,int>>edges[N + 1];
	for (int i = 0; i<M; i++){
		edges[R[i][0]].pb(mp(R[i][1], L[i]));
		edges[R[i][1]].pb(mp(R[i][0], L[i]));
	}
	int vis[N];
	
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i<K; i++){
		q.push(mp(0, P[i]));
		vis[P[i]] = 1;
	}
	while(!q.empty()){
		ll dist = q.top().fr;
		dist*=-1;
		int node = q.top().sc;
		q.pop();
		if (vis[node] == 2)continue;
		++vis[node];
		if (vis[node] != 2){
			continue;
		}
		if (node == 0){
			return (int)dist;
		}
		for (auto edge : edges[node]){
			q.push(mp(-(dist + edge.sc), edge.fr));
		}
	}
	return -1;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 1340 KB Output is correct
13 Correct 4 ms 1460 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 1340 KB Output is correct
13 Correct 4 ms 1460 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 484 ms 87424 KB Output is correct
17 Correct 81 ms 13264 KB Output is correct
18 Correct 89 ms 14832 KB Output is correct
19 Correct 492 ms 75040 KB Output is correct
20 Correct 314 ms 80248 KB Output is correct
21 Correct 42 ms 5908 KB Output is correct
22 Correct 507 ms 45380 KB Output is correct