Submission #499089

#	Time	Username	Problem	Language	Result	Execution time	Memory
499089		beksultan04	Evacuation plan (IZhO18_plan)	C++14	12 / 100	291 ms	85716 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
#define ordered_set tree <int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 1e6+12,INF = 1e15+7;
int dis[N],a[N],used[N],ans[N];
vector <pii> g[N];
set <int> s[N];
struct dsu{
	int n;
	vector<int> p;
	dsu(int N) : n(N), p(N+1) {
		for (int i=0;i<=N;++i){
			p[i] = i;
		}
	}
	
	int find_baty(int x){
		if (x == p[x])ret x;
		ret p[x] = find_baty(p[x]);
	}
	
	void merge(int a,int b,int dl){
		a = find_baty(a);
		b = find_baty(b);
		if (a == b)ret ;
		if (s[a].size() > s[b].size())swap(s[a],s[b]);
		for (auto x:s[a]){
			if (s[b].count(x)){
				ans[x] = dl;
			}
			else {
				s[b].insert(x);
			}
		}
		p[a] = b;
	}
	
	
};

bool cmp(int a,int b){
	ret dis[a]<dis[b];
}
main(){
	int n,i,m;
	cin>>n>>m;
	dsu ds(n);
	for (i=1;i<=m;++i){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].pb({y,z});
		g[y].pb({x,z});
	}
	int qq;
	cin>>qq;
	set <int,decltype(cmp)*> ss(cmp);
	for (i=1;i<=n;++i)dis[i] = INF;
	for (i=0;i<qq;++i){
		int x;
		cin>>x;
		ss.insert(x);
		dis[x] = 0;
	}
	while (!ss.empty()){
		int x = *ss.begin();
		ss.erase(ss.begin());
		for (auto [to,c]:g[x]){
			if (dis[to] > dis[x] +c){
				dis[to] = dis[x]+c;
				ss.insert(to);
			}
		}
	}
	cin>>qq;
	for (i=1;i<=qq;++i){
		int x,y;
		cin>>x>>y;
		s[x].insert(i);
		s[y].insert(i);
	} 
	vector <pii> v;
	for (i=1;i<=n;++i)
		v.pb({dis[i],i});
	sort(allr(v));
	for (auto [dl,x]: v){
		
		used[x] = 1;
		for (auto [to,asd]: g[x]){
			if (used[to]){
				ds.merge(x,to,dl);
			}
		}
		
	}
	
	for (i=1;i<=qq;++i){
		cout <<ans[i]<<" ";
	}
	
	
}

Compilation message (stderr)

plan.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main(){
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:83:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for (auto [to,c]:g[x]){
      |             ^
plan.cpp:101:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |  for (auto [dl,x]: v){
      |            ^
plan.cpp:104:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |   for (auto [to,asd]: g[x]){
      |             ^

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