Submission #24935840

---

Source Code Expand

#include "bits/stdc++.h"

#define int long long

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = (1LL << 61);
ll mod = 1000000007;

int N, M;
vector<int>G[200010], G2[200010];
int c[200010];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	vector<int>A(M), B(M);
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
		A[i] = a, B[i] = b;
	}
	int T = sqrt(2 * M * 100);
	vector<bool>is_big(N);
	for (int i = 0; i < N; i++) {
		if ((int)(G[i].size()) >= T) {
			is_big[i] = true;
		}
	}
	for (int i = 0; i < M; i++) {
		if (is_big[B[i]])G2[A[i]].push_back(B[i]);
		if (is_big[A[i]])G2[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; i++)c[i] = 1;
	int Q; cin >> Q;
	vector<int>x(Q), y(Q);
	vector<int>wh(N, -1);
	for (int i = 0; i < Q; i++) {
		cin >> x[i] >> y[i]; x[i]--;
		if (is_big[x[i]]) {
			cout << c[x[i]] << endl;
			c[x[i]] = y[i];
			for (auto nv : G2[x[i]]) {
				c[nv] = y[i];
			}
		}
		else {
			int now = -1;
			now = max(now, wh[x[i]]);
			for (auto nv : G[x[i]]) {
				now = max(now, wh[nv]);
			}
			if (now == -1)cout << 1 << endl;
			else cout << y[now] << endl;
			c[x[i]] = y[i];
			for (auto nv : G2[x[i]]) {
				c[nv] = y[i];
			}
		}
		wh[x[i]] = i;
	}
	return 0;


}

Submission Info

Judge Result