Submission #378796

#	Time	Username	Problem	Language	Result	Execution time	Memory
378796		rk42745417	Evacuation plan (IZhO18_plan)	C++17	31 / 100	468 ms	20004 KiB

plan

#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;
#define EMT ios::sync_with_stdio(0); cin.tie(0);

const int N = 1e5 + 25;
int dis[N];
bool vis[N];
vector<int> npp;
vector<pair<int, int>> edge[N];

struct DisjointSet {
	int pa[N], sz[N];
	stack<pair<int, int>> st;
	void init(int n) {
		for(int i = 1; i <= n; i++)
			sz[i] = 1, pa[i] = i;
	}
	int fnd(int x) { return pa[x] == x ? pa[x] : fnd(pa[x]); }
	bool uni(int a, int b) {
		if((a = fnd(a)) == (b = fnd(b)))
			return false;
		if(sz[a] > sz[b])
			swap(a, b);
		sz[b] += sz[a];
		pa[a] = b;
		st.push({a, b});
		return true;
	}
	void undo() {
		assert(st.size());
		auto [a, b] = st.top();
		st.pop();
		pa[a] = a;
		sz[b] -= sz[a];
	}
} dsu;
void solve() {
	memset(dis, 0x3f, sizeof dis);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int a : npp)
		dis[a] = 0, pq.push({dis[a], a});
	while(!pq.empty()) {
		auto [c, u] = pq.top();
		pq.pop();
		if(c > dis[u])
			continue;
		for(const auto &[v, d] : edge[u]) {
			if(dis[v] > c + d) {
				dis[v] = c + d;
				pq.push({dis[v], v});
			}
		}
	}
};
const int SQN = 350;
signed main() { EMT
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edge[u].push_back({v, w});
		edge[v].push_back({u, w});
	}

	int k;
	cin >> k;
	npp.resize(k);
	for(int &a : npp)
		cin >> a;
	
	solve();
	dsu.init(n);
	
	int q;
	cin >> q;
	vector<pair<int, int>> arr(n);
	set<tuple<int, int, int>> que;
	vector<int> ans(q);
	for(int i = 0, a, b; i < q; i++) {
		cin >> a >> b;
		que.insert({a, b, i});
	}

	for(int i = 1; i <= n; i++)
		arr[i - 1] = {dis[i], i};
	sort(arr.begin(), arr.end(), greater<pair<int, int>>());
	vector<tuple<int, int, int>> owo;
	for(int i = 0; i < n; i++) {
		int u = arr[i].second;
		vis[u] = 1;
		for(const auto &[v, d] : edge[u])
			if(vis[v])
				if(dsu.uni(u, v))
					owo.push_back({u, v, arr[i].first});
		if((owo.size() && owo.size() % SQN == 0) || owo.size() == n - 1) {
			vector<tuple<int, int, int>> tmp;
			for(const auto &[a, b, id] : que)
				if(dsu.fnd(a) == dsu.fnd(b))
					tmp.push_back({a, b, id});
			for(int i = 0; i < owo.size(); i++)
				dsu.undo();
			//cerr << "here\n";

			for(const auto &[u, v, w] : owo) {
				dsu.uni(u, v);
				for(const auto &[a, b, id] : tmp) {
					if(dsu.fnd(a) == dsu.fnd(b))
						ans[id] = max(ans[id], w);
				}
			}
			for(const auto &e : tmp)
				que.erase(e);
			//cerr << "here\n";

			owo.clear();
		}
		//cerr << "XDD " << i << '\n';
	}
	//cerr << "here\n";
	for(int a : ans)
		cout << a << '\n';
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5

*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:105:58: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |   if((owo.size() && owo.size() % SQN == 0) || owo.size() == n - 1) {
      |                                               ~~~~~~~~~~~^~~~~~~~
plan.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for(int i = 0; i < owo.size(); i++)
      |                   ~~^~~~~~~~~~~~

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