oj.uz

Submission #990238

# Submission time Handle Problem Language Result Execution time Memory
990238 2024-05-30T00:16:42 Z SN0WM4N Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 623 ms 119728 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

#pragma GCC optimize("O3")

#ifdef LOCAL 
	#include "debug.h"
#else 
	#define dbg(...) 0
#endif

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 1e9 + 7; //[998244353, 1e9 + 7, 1e9 + 13]
const ld PI = acos(-1);
const ll NROOT = 500;

ll binpow(ll a, ll b, ll _MOD = -1) {
	if (_MOD == -1)
		_MOD = MOD;
	ll res = 1;
	for (; b; b /= 2, a *= a, a %= _MOD)
		if (b & 1) res *= a, res %= _MOD;
	return res;
}

void set_IO(string s) {
#ifndef LOCAL
	string in  = s +  ".in";
	string out = s + ".out";
	freopen(in.c_str(),  "r",  stdin);
	freopen(out.c_str(), "w", stdout);
#endif
}

bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}
ll invmod(ll a) {return binpow(a, MOD - 2);}

int n, m, k;
vector<int> spec;
vector<vector<pair<int, ll>>> g; 

bool cmp(pair<int, ll> a, pair<int, ll> b) {
	if (a.S == b.S)
		return a.F < b.F;
	return a.S < b.S;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N;
	m = M;

	g.resize(n + 1);

	for (int i = 0; i < m; i ++) {
		int a = R[i][0] + 1;
		int b = R[i][1] + 1;
		int c = L[i];

		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}

	k = K;
	vector<int> vis(n + 1), dis(n + 1, inf);
	using T = pair<ll, int>;
	priority_queue<T, vector<T>, greater<T>> q;

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

	while (!q.empty()) {
		auto [d, x] = q.top();
		q.pop();

		if (dis[x] <= d)
			continue;
		vis[x] ++;
		if (vis[x] != 2) 
			continue;
		dis[x] = d;

		for (auto &y : g[x]) 
			q.push({d + y.S, y.F});
	}

	return dis[1];
}

#ifdef LOCAL
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M, K;
	cin >> N >> M >> K;

	int R[M][2], L[M], P[K];

	for (int i = 0; i < M; i ++) 
		cin >> R[i][0] >> R[i][1] >> L[i];
	for (int i = 0; i < K; i ++)
		cin >> P[i];

	cout << travel_plan(N, M, R, L, K, P) << "\n";

	return 0;
}
#endif

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:94:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |   auto [d, x] = q.top();
      |        ^
crocodile.cpp: In function 'void set_IO(std::string)':
crocodile.cpp:46:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  freopen(in.c_str(),  "r",  stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:47:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  freopen(out.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 5 ms 5596 KB Output is correct
13 Correct 6 ms 5860 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 5 ms 5596 KB Output is correct
13 Correct 6 ms 5860 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 592 ms 113832 KB Output is correct
17 Correct 53 ms 18732 KB Output is correct
18 Correct 74 ms 21076 KB Output is correct
19 Correct 623 ms 119728 KB Output is correct
20 Correct 475 ms 100268 KB Output is correct
21 Correct 29 ms 10844 KB Output is correct
22 Correct 425 ms 65048 KB Output is correct