제출 #989902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989902		SN0WM4N	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	1 ms	4440 KiB

crocodile

#include <bits/stdc++.h>
#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")

using namespace std;

const ll inf = 2147483647;

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;
	for (int i = 0; i < k; i ++) 
		spec.push_back(P[i] + 1);

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

	for (auto &x : g)
		stable_sort(x.begin(), x.end(), cmp);
	for (auto &x : spec)
		q.push({0, x});

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

		if (dis1[x] <= d)
			continue;
		dis1[x] = d;

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

	vector<int> dis2(n + 1, inf);

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

		if (dis2[x] <= d)
			continue;
		dis2[x] = d;

		vector<pair<pair<ll, ll>, pair<int, ll>>> ways;

		for (auto &y : g[x]) 
			ways.push_back({{dis1[y.F], y.S}, y});
		stable_sort(ways.begin(), ways.end());

		for (int i = 1; i < ways.size(); i ++) {
			pair<int, ll> y = ways[i].S;
			q.push({d + y.S, y.F});
		}
	}

	int ans = inf;
	for (auto &x : spec) 
		ans = min(ans, dis2[x]);

  	if (ans == inf)
      	exit(1);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:56:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |   auto [d, x] = q.top();
      |        ^
crocodile.cpp:72:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   auto [d, x] = q.top();
      |        ^
crocodile.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int i = 1; i < ways.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11