oj.uz

Submission #990239

# Submission time Handle Problem Language Result Execution time Memory
990239 2024-05-30T00:17:23 Z vjudge1 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 608 ms 102688 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 '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 4444 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 4444 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 1 ms 4532 KB Output is correct
12 Correct 5 ms 5596 KB Output is correct
13 Correct 4 ms 5604 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 1 ms 4532 KB Output is correct
12 Correct 5 ms 5596 KB Output is correct
13 Correct 4 ms 5604 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 551 ms 97032 KB Output is correct
17 Correct 52 ms 15440 KB Output is correct
18 Correct 83 ms 17512 KB Output is correct
19 Correct 608 ms 102688 KB Output is correct
20 Correct 413 ms 88248 KB Output is correct
21 Correct 28 ms 9564 KB Output is correct
22 Correct 381 ms 50984 KB Output is correct