Submission #1124109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124109		KasymK	Evacuation plan (IZhO18_plan)	C++17	100 / 100	769 ms	71520 KiB

plan

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 1e5+5;
const ll INF = 1e18;
ll ans[N], dis[N];
map<pii, vector<int>> mp;
set<int> mal[N], S[N];
int rep[N];
vector<pii> adj[N];
bool act[N], is[N];

int find(int x){
	if(rep[x]==x)
		return x;
	return rep[x]=find(rep[x]);
}

void merge(int x, int y, ll val){
	x=find(x), y=find(y);
	if(x==y)
		return;
	if((int)S[x].size()<(int)S[y].size())
		swap(x, y);
	rep[y] = x;
	tr(it, S[y])
	tr(ii, mal[*it]){
		if(S[x].count(*ii)){
			vector<int> A = mp[{*ii, *it}];
			tr(wow, A){
				if(is[*wow])
					continue;
				is[*wow]=1;
				ans[*wow]=val;
			}
		}
		else
			S[x].insert(*it);
	}
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	for(int i = 1; i <= n; ++i)
		dis[i] = INF, rep[i] = i, S[i].insert(i);
	int k;
	scanf("%d", &k);
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	for(int i = 1; i <= k; ++i){
		int x;
		scanf("%d", &x);
		dis[x] = 0;
		pq.push({0, x});
	}
	while(!pq.empty()){
		int x = pq.top().ss;
		ll val = pq.top().ff;
		pq.pop();
		if(dis[x]!=val)
			continue;
		tr(it, adj[x])
		if(umin(dis[it->ff], dis[x]+it->ss))
			pq.push({dis[it->ff], it->ff});
	}
	int q;
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i){
		int s, t;
		scanf("%d%d", &s, &t);
		mal[s].insert(t);
		mal[t].insert(s);
		mp[{s, t}].pb(i);
		mp[{t, s}].pb(i);
	}
	vector<pli> ad;
	for(int i = 1; i <= n; ++i)
		ad.pb({dis[i], i});
	sort(all(ad));
	reverse(all(ad));
	// tr(d, ad)
	// printf("NPP->%d = %lld\n", d->ss, d->ff);
	// wr;
	tr(d, ad){
		act[d->ss]=1;
		tr(i, adj[d->ss])
		if(act[i->ff])
			merge(d->ss, i->ff, d->ff);
	}
	for(int i = 1; i <= q; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 scanf("%d%d%d", &a, &b, &c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
plan.cpp:69:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |                 scanf("%d", &x);
      |                 ~~~~~^~~~~~~~~~
plan.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
plan.cpp:87:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 scanf("%d%d", &s, &t);
      |                 ~~~~~^~~~~~~~~~~~~~~~

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