Submission #632947

#	Time	Username	Problem	Language	Result	Execution time	Memory
632947		NintsiChkhaidze	Evacuation plan (IZhO18_plan)	C++14	100 / 100	578 ms	53784 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,int>> v[N],qr[N],vec;
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){
	int px = P(x),py = P(y);
	if (px == py) return;

	if (qr[px].size() < qr[py].size()) swap(px,py);
	par[py] = px;

	for (auto [to,id]: qr[py]){
		if (P(py) == P(to)) ans[id] = max(ans[id],W);
		else qr[px].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,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 <int,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()){
		int 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});
	}
	
	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:29:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |  for (auto [to,id]: qr[py]){
      |            ^
plan.cpp: In function 'int main()':
plan.cpp:65:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   for (auto [to,w]: v[x]){
      |             ^
plan.cpp:86:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |  for (auto [d,x]: vec){
      |            ^
plan.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [to,w]: v[x])
      |             ^

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