oj.uz

Submission #722042

# Submission time Handle Problem Language Result Execution time Memory
722042 2023-04-11T10:51:16 Z Zflop Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 791 ms 61336 KB 
#include <bits/stdc++.h>
using namespace std;

using str = string; // yay python!
using ld = long double; // or double, if TL is tight
using ll = long long;
using int64 = ll;
using db = double;
using ull = unsigned long long;
 
#define ch() getchar()
#define pc(x) putchar(x)
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pair<int,int>>;
using vvi = V<vi>;
using vl = V<ll>;
using vd = V<ld>;
using vstr = V<str>;

// pairs
#define mp make_pair
#define pi pair <int, int>
#define f first
#define s second

// loops
#define F0R(i, a, b) for (int i=a; i<b;++i)
#define FOR(i, a) for (int i=0; i<a;++i)
#define FORn(i, a) for (int i=1; i<=a;++i)
#define ROF(i,a) for(int i=a-1; i >= 0;--i)
#define R0F(i,a,b) for(int i=a; i > b;--i)
#define ROFn(i,a) for(int i=a; i > 0;--i)
#define rep(a) F0R(_, a)
#define trav(i,x) for(auto& i:x)

// vectors
#define lb lower_bound
#define ub upper_bound
#define SUM(v) accumulate(all(v), 0LL)
#define MN(v) *min_element(all(v))
#define MX(v) *max_element(all(v))
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define eb emplace_back
#define ft front()
#define bk back()
#define ins insert
#define pf push_front
#define pb push_back
#define emt empty()
#define rsz resize

#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define sz(x) (int)(x).size()
#define rall(x) x.rbegin(), x.rend()
#define AR array

const ll inf = (ll)1e14;
int travel_plan(int N, int M,int in[][2], int tm[], int K,int r[]);
int travel_plan(int N, int M,int in[][2], int tm[], int K,int r[]){
	V<vpi> A(N + 1);
	FOR(i,M){
		int a = in[i][0];
		int b = in[i][1];
		int c = tm[i];
		A[a].pb({b,c});
		A[b].pb({a,c});
		}
	
	auto djs = [&] (){
		V<pair<ll,ll>> cost(N,{inf,inf});
		priority_queue<vl,V<vl>,greater<vl>>pq;
		FOR(i,K){
			cost[r[i]] = {0,0};
			pq.push({0,0,r[i]});
			}
		while(sz(pq)){
			auto node = pq.top();
			ll a = node[0];
			ll b = node[1];
			ll c = node[2];
			pq.pop();
			if(cost[c].f < a || a == inf) continue;
			if(cost[c].f == a && cost[c].s < b) continue;
			trav(x,A[c])
				if(cost[x.f].s > a + x.s){
					cost[x.f].f = cost[x.f].s;
					cost[x.f].s = a + x.s;
					pq.push({cost[x.f].f,cost[x.f].s,x.f});
					}
				else if(cost[x.f].f > a + x.s){
					cost[x.f].f = a + x.s;
					pq.push({cost[x.f].f,cost[x.f].s,x.f});
					}
			}
		return cost[0].f;
		};
	return djs();
}

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 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 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 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 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 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 544 ms 46364 KB Output is correct
17 Correct 124 ms 16636 KB Output is correct
18 Correct 233 ms 17664 KB Output is correct
19 Correct 791 ms 61336 KB Output is correct
20 Correct 251 ms 34032 KB Output is correct
21 Correct 49 ms 6492 KB Output is correct
22 Correct 291 ms 32116 KB Output is correct