Submission #990237

#	Time	Username	Problem	Language	Result	Execution time	Memory
990237		SN0WM4N	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	1 ms	4444 KiB

crocodile

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

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |       auto [d, x] = q.top();
      |            ^
crocodile.cpp:73:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |       auto [d, x] = q.top();
      |            ^
crocodile.cpp:86:25: 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]
   86 |       for (int i = 1; i < ways.size(); i ++) {
      |                       ~~^~~~~~~~~~~~~

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