Submission #632944

#	Time	Username	Problem	Language	Result	Execution time	Memory
632944		NintsiChkhaidze	Evacuation plan (IZhO18_plan)	C++14	19 / 100	399 ms	38412 KiB

plan

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define ll long long
#define int ll
using namespace std;

const int N = 100005;
vector <pair <int,ll>> v[N],qr[N];
ll dis[N];
bool vis[N];
int par[N],ans[N],W;

int P(int x){
	if (x == par[x]) return x;
	return par[x] = P(par[x]);
}
void dsu(int x,int y){
	x = P(x),y = P(y);
	if (x == y) return;

	if (qr[x].size() < qr[y].size()) swap(x,y);
	par[y] = x;

	for (auto [to,id]: qr[y]){
		if (P(y) == P(to)) ans[id] = W;
		else qr[x].pb({to,id});
	}
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m;
	cin>>n>>m;

	for (int i = 1; i <= m; i++){
		int a,b; ll c;
		cin>>a>>b>>c;
		v[a].pb({b,c});
		v[b].pb({a,c});
	}

	for (int i = 1; i <= n; i++)
		dis[i] = 1e18,par[i] = i;

	using T = pair <ll,int>;
	priority_queue <T, vector <T>, greater <T> > pq;
	int k;
	cin>>k;
	for (int i = 1; i <= k; i++){
		int x;
		cin>>x;
		dis[x] = 0LL;
		pq.push({0LL,x});
	}

	while (pq.size()){
		ll d = pq.top().f,x = pq.top().s;
		pq.pop();
		if (dis[x] != d) continue;
		for (auto [to,w]: v[x]){
			if (dis[to] > d + w){
				dis[to] = d + w;
				pq.push({d + w,to});
			}
		}
	}
	int Q;
	cin>>Q;

	for (int i = 1; i <= Q; i++){
		int s,t;
		cin>>s>>t;
		qr[s].pb({t,i});
		qr[t].pb({s,i});
	}
	vector <pair <int,int> > vec; vec.clear();
	for (int i = 1; i <= n; i++)
		vec.pb({dis[i],i});

	sort(vec.begin(),vec.end(), greater <pair <int,int>> ());
	for (auto [d,x]: vec){
		vis[x] = 1;
		W = d;
		for (auto [to,w]: v[x])
			if (vis[to]) dsu(x,to);
	}
	for (int i = 1; i <= Q; i++)
		cout<<ans[i]<<endl;
}

Compilation message (stderr)

plan.cpp: In function 'void dsu(long long int, long long int)':
plan.cpp:28:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |  for (auto [to,id]: qr[y]){
      |            ^
plan.cpp: In function 'int main()':
plan.cpp:63:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |   for (auto [to,w]: v[x]){
      |             ^
plan.cpp:84:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |  for (auto [d,x]: vec){
      |            ^
plan.cpp:87:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |   for (auto [to,w]: v[x])
      |             ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46