oj.uz

답안 #709659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709659 2023-03-14T06:47:10 Z ono_de206 악어의 지하 도시 (IOI11_crocodile) C++14
89 / 100
 555 ms 73708 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];

ll 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(cs + t < dp[y][0]) {
				if(dp[y][0] != inf) {
					dp[y][1] = dp[y][0];
					q.push({dp[y][1], y});
				}
				dp[y][0] = cs + t;
			}
			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';
	// }
	assert(dp[0][1] != inf);
	return dp[0][1];
}

Compilation message

crocodile.cpp: In function 'll 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 4 ms 3284 KB Output is correct
13 Correct 4 ms 3388 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 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 4 ms 3284 KB Output is correct
13 Correct 4 ms 3388 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 382 ms 67128 KB Output is correct
17 Correct 78 ms 15112 KB Output is correct
18 Correct 98 ms 17352 KB Output is correct
19 Correct 555 ms 73708 KB Output is correct
20 Correct 271 ms 55140 KB Output is correct
21 Correct 37 ms 8576 KB Output is correct
22 Incorrect 292 ms 50172 KB Output isn't correct
23 Halted 0 ms 0 KB -