Submission #50850

#	Time	Username	Problem	Language	Result	Execution time	Memory
50850		Nicksechko	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1252 ms	55440 KiB

plan

#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 220000;
const int LOG = 20;
const int INF = 2e9 + 10000;

int p[MAXN];
int sz[MAXN];
vector<pair<int, int> > eds[MAXN];
vector<int> eee[MAXN];
vector<tuple<int, int, int> > ed;
int dd[MAXN];
set<pair<int, int> > ss;
int fl[MAXN];
int tin[MAXN];
int tout[MAXN];
int tm1;
int up[LOG][MAXN];
int upp[LOG][MAXN];

int n, m;

int get(int a) {
	if (p[a] == a)
		return a;
	return p[a] = get(p[a]);
}

int un(int a, int b) {
	a = get(a);
	b = get(b);
	if (a == b)
		return 0;
	if (sz[a] > sz[b])
		swap(a, b);
	p[a] = b;
	sz[b] += sz[a];
	return 1;
}

void dfs1(int v, int p) {
	tin[v] = tm1++;
	up[0][v] = p;
	upp[0][v] = min(dd[v], dd[p]);
	for (int i = 1; i < LOG; ++i) {
		up[i][v] = up[i - 1][up[i - 1][v]];
		upp[i][v] = min(upp[i - 1][v], upp[i - 1][up[i - 1][v]]);
	}
	for (int u: eee[v]) {
		if (u == p)
			continue;
		dfs1(u, v);
	}
	tout[v] = tm1;
}

int is_p(int a, int b) {
	return (tin[a] <= tin[b] && tin[b] < tout[a]);
}

int lca(int a, int b) {
	if (is_p(a, b))
		return a;
	if (is_p(b, a))
		return b;
	for (int i = LOG - 1; i >= 0; --i) {
		if (!is_p(up[i][a], b))
			a = up[i][a];
	}
	return up[0][a];
}

int gett(int a, int b) {
	int ans = min(dd[a], dd[b]);
	for (int i = LOG - 1; i >= 0; --i) {
		if (is_p(b, up[i][a]))
			ans = min(ans, upp[i][a]), a = up[i][a];
	}
	return ans;
}

int get(int a, int b) {
	int x = lca(a, b);
	return min(gett(a, x), gett(b, x));
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		--a, --b;
		eds[a].push_back(make_pair(b, c));
		eds[b].push_back(make_pair(a, c));
	}
	for (int i = 0; i < n; ++i)
		dd[i] = INF;
	int k;
	scanf("%d", &k);
	for (int i = 0; i < k; ++i) {
		int x;
		scanf("%d", &x);
		--x;
		fl[x] = 1;
		dd[x] = 0;
		ss.insert(make_pair(0, x));
	}
	while (!ss.empty()) {
		int x = ss.begin()->second;
		ss.erase(ss.begin());
		for (auto e: eds[x]) {
			int u = e.first;
			if (dd[u] > dd[x] + e.second) {
				ss.erase(make_pair(dd[u], u));
				dd[u] = dd[x] + e.second;
				ss.insert(make_pair(dd[u], u));
			}
		}
	}
	for (int i = 0; i < n; ++i)
		p[i] = i, sz[i] = 1;
	for (int i = 0; i < n; ++i) {
		for (auto e: eds[i]) {
			if (e.first > i)
				ed.push_back(make_tuple(min(dd[i], dd[e.first]), i, e.first));
		}
	}
	sort(ed.rbegin(), ed.rend());
	for (int i = 0; i < ed.size(); ++i) {
		int a, b, len;
		tie(len, a, b) = ed[i];
		if (un(a, b))
			eee[a].push_back(b), eee[b].push_back(a);
	}
	dfs1(0, 0);
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		printf("%d\n", get(a, b));
	}
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:148:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ed.size(); ++i) {
                  ~~^~~~~~~~~~~
plan.cpp:107: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:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
plan.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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