oj.uz

Submission #709656

# Submission time Handle Problem Language Result Execution time Memory
709656 2023-03-14T06:32:45 Z ono_de206 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 471 ms 73912 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 1e5 + 10;
const ll inf = 1e18 + 10;
int n;
ll dp[mxn][3];
vector<pair<int, ll>> g[mxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N;
	for(int i = 0; i < M; i++) {
		int x = R[i][0];
		int y = R[i][1];
		int t = L[i];
		g[x].pb({y, t});
		g[y].pb({x, t});
	}
	for(int i = 0; i < n; i++) {
		dp[i][0] = dp[i][1] = inf;
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	for(int i = 0; i < K; i++) {
		dp[P[i]][0] = dp[P[i]][1] = 0;
		q.push({0, P[i]});
	}
	while(q.size()) {
		ll cs = q.top().ff;
		int x = q.top().ss;
		q.pop();
		if(dp[x][1] != cs) continue;
		for(auto [y, t] : g[x]) {
			if(dp[y][0] == inf) {
				dp[y][0] = cs + t;
			}
			else if(cs + t < dp[y][0]) {
				dp[y][1] = dp[y][0];
				dp[y][0] = cs + t;
				q.push({dp[y][1], y});
			}
			else if(cs + t < dp[y][1]) {
				dp[y][1] = cs + t;
				q.push({dp[y][1], y});
			}
		}
	}
	// for(int i = 0; i < n; i++) {
	// 	cout << dp[i][0] << ' ' << dp[i][1] << '\n';
	// }
	return (int)dp[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |   for(auto [y, t] : g[x]) {
      |            ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 6 ms 3284 KB Output is correct
13 Correct 4 ms 3284 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 6 ms 3284 KB Output is correct
13 Correct 4 ms 3284 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 367 ms 67172 KB Output is correct
17 Correct 67 ms 15112 KB Output is correct
18 Correct 101 ms 17484 KB Output is correct
19 Correct 471 ms 73912 KB Output is correct
20 Correct 316 ms 54988 KB Output is correct
21 Correct 31 ms 8448 KB Output is correct
22 Incorrect 259 ms 50140 KB Output isn't correct
23 Halted 0 ms 0 KB -