oj.uz

Submission #508800

# Submission time Handle Problem Language Result Execution time Memory
508800 2022-01-13T19:38:29 Z silverfish Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 805 ms 101472 KB 
#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

/*<DEBUG>*/
#define tem template <typename 
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
	~debug(){ cerr << endl; }
	tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
	tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
	tem T, typename U > _op (pair<T, U> i){ 
		return *this << "< " << i.first << " , " << i.second << " >"; }
	tem T> _op (itr<T> i){
		*this <<  "{ ";
		for(auto it = i.begin; it != i.end; it++){
			*this << " , " + (it==i.begin?2:0) << *it;
		}
		return *this << " }";
	}
#else
tem T> _op (const T&) { return *this; }
#endif 
};

tem T>
string _ARR_(T* arr, int sz){
	string ret = "{ " + to_string(arr[0]); 
	for(int i = 1; i < sz; i++) ret += " , " +  to_string(arr[i]);
	ret += " }"; return ret;
}

#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array

const int N = 100005, INF = 1000000009;

struct edge{
	ll to, w; 
};

ll dp[N], vis[N];
vector<edge> adj[N];

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({r[i][1], l[i]});
		adj[r[i][1]].pb({r[i][0], l[i]});
	}

	fill(dp, dp+n+1, INF);

	priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> q;

	for(int i = 0; i < k; ++i){
		vis[p[i]] = 1;
		dp[p[i]] = 0;
		q.push({0, p[i]});
	}

	while(q.size()){
		auto [w, u] = q.top();
		q.pop();

		if(vis[u] == 2) continue;

		if(!vis[u]){
			vis[u] = 1;
			continue;
		}

		if(vis[u] == 1){
			dp[u] = w;
			vis[u] = 2;
		}


		for(auto [v, cw] : adj[u]){
			if(vis[v] != 2) q.push({dp[u] + cw, v});
		}

	}

	return dp[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 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 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 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 9 ms 3660 KB Output is correct
13 Correct 7 ms 3740 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 2 ms 2764 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 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 9 ms 3660 KB Output is correct
13 Correct 7 ms 3740 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 721 ms 81140 KB Output is correct
17 Correct 83 ms 17600 KB Output is correct
18 Correct 117 ms 20032 KB Output is correct
19 Correct 805 ms 101472 KB Output is correct
20 Correct 562 ms 84524 KB Output is correct
21 Correct 42 ms 9720 KB Output is correct
22 Correct 481 ms 64448 KB Output is correct