Submission #3025117

---

Source Code Expand

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

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
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 = 120000;

int n, m;
ll a[MAXN];
ll b[MAXN];
int en[MAXN];
int p[MAXN];
int sz[MAXN];

vector<int> eds[MAXN];

set<pair<ll, int> > ss[MAXN];
ll sum[MAXN];

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

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		a[i] = max(a[i], b[i]);
	}
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	ll l = -1;
	ll r = 1e9;
	while (r - l > 1) {
		ll mid = (l + r) >> 1;
		fill(en, en + n, 0);
		iota(p, p + n, 0);
		for (int i = 0; i < n; ++i)
			ss[i].clear();
		for (int i = 0; i < n; ++i) {
			if (!en[i] && a[i] <= b[i] + mid) {
				en[i] = 1;
				sum[i] = mid + b[i];
				queue<int> qu;
				qu.push(i);
				while (!qu.empty()) {
					int x = qu.front();
					qu.pop();
					for (int j: eds[x])
						if (get(j) != i)
							ss[i].emplace(a[j] - b[j], j);
					while (!ss[i].empty() && ss[i].begin()->first <= sum[i]) {
						int x = ss[i].begin()->second;
						ss[i].erase(ss[i].begin());
						if (!en[x]) {
							sum[i] += b[x];
							en[x] = 1;
							p[x] = i;
							qu.push(x);
						}
						else {
							x = get(x);
							if (x == i)
								continue;
							sum[i] += sum[x] - mid;
							if (ss[x].size() > ss[i].size())
								swap(ss[x], ss[i]);
							for (auto e: ss[x])
								ss[i].insert(e);
							ss[x].clear();
							p[x] = i;
						}
					}
				}
			}
		}
		if (accumulate(en, en + n, 0) == n)
			r = mid;
		else
			l = mid;
	}
	cout << r + accumulate(b, b + n, 0ll) << "\n";
	return 0;
}

Submission Info

Judge Result