이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
int n, q;
const int maxn = 4e5 + 4;
bool mark[maxn]; queue<int> qu;
int p[maxn]; ll val[maxn]; vector<pii> E;
vector<int> ls[maxn]; set<int> A[maxn];
set<int> adj[maxn], adjr[maxn]; ll res = 0;
ll cal(ll sz, ll t) {
return (sz * t) + sz * (sz - 1);
}
void upd(int a) {
res -= val[a];
val[a] = cal(len(ls[a]), len(A[a]));
res += val[a];
}
int get(int a) {
return p[a];
}
bool ok(int a, int b) {
a = get(a); b = get(b);
if (a != b && adj[a].find(b) != adj[a].end() && adj[b].find(a) != adj[b].end()) return 1;
return 0;
}
void merge(int a1, int b1) {
qu.push(b1); mark[b1] = 1;
while (!qu.empty()) {
int b1 = qu.front(); mark[b1] = 0;
qu.pop();
int a = get(a1), b = get(b1);
if (a == b) continue;
if (len(ls[a]) > len(ls[b])) swap(a, b);
for (int v : A[a]) {
if (p[v] == a || p[v] == b) continue;
A[b].insert(v);
}
A[a].clear();
for (int v : ls[a]) {
p[v] = b; ls[b].pb(v);
A[b].erase(v);
}
ls[a].clear();
for (int v : adj[a]) {
if (v == a || v == b) continue;
adj[b].insert(v);
adjr[v].erase(a); adjr[v].insert(b);
}
for (int v : adjr[a]) {
if (v == a || v == b) continue;
adjr[b].insert(v);
adj[v].erase(a); adj[v].insert(b);
}
adj[b].erase(a); adjr[b].erase(a);
for (int v : adj[a]) {
if (ok(b, v) && !mark[v]) {
qu.push(v); mark[v] = 1;
}
}
for (int v : adjr[a]) {
if (ok(b, v) && !mark[v]) {
qu.push(v); mark[v] = 1;
}
}
adj[a].clear(); adjr[a].clear();
upd(a), upd(b);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 0; i < n; i++) {
p[i] = i; ls[i].pb(i);
}
for (int i = 0; i < q; i++) {
int u1, v1;
cin >> u1 >> v1; u1--; v1--;
E.pb(Mp(u1, v1));
int u = get(u1), v = get(v1);
if (u == v) {
cout << res << endl;
continue;
}
A[v].insert(u1);
upd(v);
adj[u].insert(v); adjr[v].insert(u);
if (ok(u, v)) merge(u, v);
cout << res << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |