oj.uz

Submission #709653

# Submission time Handle Problem Language Result Execution time Memory
709653 2023-03-14T06:30:42 Z ono_de206 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 489 ms 45208 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, inf = 1e9 + 10;
int n, dp[mxn][3];
vector<pair<int, int>> 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<int, int>, vector<pair<int, int>>, greater<pair<int, 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()) {
		int 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 dp[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:75:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   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 1 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2644 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 1 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 3 ms 2772 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 4 ms 3028 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 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 1 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 3 ms 2772 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 5 ms 3028 KB Output is correct
13 Correct 4 ms 3028 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 395 ms 41408 KB Output is correct
17 Correct 67 ms 10780 KB Output is correct
18 Correct 86 ms 12072 KB Output is correct
19 Correct 489 ms 45208 KB Output is correct
20 Correct 283 ms 36544 KB Output is correct
21 Correct 33 ms 6356 KB Output is correct
22 Incorrect 259 ms 31932 KB Output isn't correct
23 Halted 0 ms 0 KB -