Submission #50846

#	Time	Username	Problem	Language	Result	Execution time	Memory
50846		Nicksechko	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1070 ms	57100 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#ifdef WIN32
	#define I64 "%I64d"
#else
	#define I64 "%lld"
#endif

typedef long long ll;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"
#define MAXN 100001
#define MAXM 500005

const int INF = int(1e9);

int n, m, k, qq;
vector < pair<int, int> > g[MAXN];
int d[MAXN];
priority_queue < pair<int, int> > q;
int ans[MAXN];
vector < pair<int, pair<int, int> > > e;
unordered_set <int> u[MAXN];
int c[MAXN];

inline int getp(int v) {
	return c[v] == v ? v : c[v] = getp(c[v]);
}

int main()
{
	#ifdef LOCAL
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	#endif

	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int v1, v2, cost;
		scanf("%d%d%d", &v1, &v2, &cost);
		--v1, --v2;
		g[v1].pb({v2, cost});
		g[v2].pb({v1, cost});
	}

	for (int i = 0; i < n; ++i) {
		d[i] = INF;
	}

	scanf("%d", &k);
	for (int i = 0; i < k; ++i) {
		int x;
		scanf("%d", &x);
		--x;
		d[x] = 0;
		q.push({-d[x], x});
	}

	while(!q.empty()) {
		int dist = -q.top().f;
		int v = q.top().s;
		q.pop();
		if (dist != d[v]) continue;
		for (const auto& t : g[v]) {
			int v2 = t.f;
			int cost = t.s;
			if (d[v2] > d[v] + cost) {
				d[v2] = d[v] + cost;
				q.push({-d[v2], v2});
			}
		}
	}

	scanf("%d", &qq);
	for (int i = 0; i < qq; ++i) {
		int v1, v2;
		scanf("%d%d", &v1, &v2);
		--v1, --v2;
		u[v1].insert(i);
		u[v2].insert(i);
	}

	for (int i = 0; i < n; ++i) {
		c[i] = i;
		for (const auto& ed : g[i]) {
			e.pb(mp(min(d[i], d[ed.f]), mp(i, ed.f)));
		}
	}

	sort(all(e));

	for (int i = sz(e) - 1; i >= 0; --i) {
		int cost = e[i].f;
		int v1 = getp(e[i].s.f);
		int v2 = getp(e[i].s.s);
		if (v1 == v2) continue;
		if (sz(u[v1]) < sz(u[v2])) swap(v1, v2);
		for (const int& ind : u[v2]) {
			if (u[v1].count(ind)) {
				ans[ind] = cost;
				u[v1].erase(ind);
			} else {
				u[v1].insert(ind);
			}
		}
		c[v2] = v1;
	}

	for (int i = 0; i < qq; ++i) {
		printf("%d\n", ans[i]);
	}

	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v1, &v2, &cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &qq);
  ~~~~~^~~~~~~~~~~
plan.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v1, &v2);
   ~~~~~^~~~~~~~~~~~~~~~~~

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