// 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 = 50 + 4;
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];
}
void merge(int a, int b) {
a = get(a); b = get(b);
if (a == b) return ;
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);
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) continue;
A[v].insert(u1);
upd(v);
adj[u].insert(v); adjr[v].insert(u);
//if (adj[v].find(u) != adj[v].end()) merge(u, v);
while (true) {
pii R = Mp(-1, -1);
for (auto f : E) {
int u = f.F, v = f.S;
u = get(u); v = get(v);
if (u == v) continue;
if (adj[v].find(u) != adj[v].end()) R = Mp(u, v);
}
if (R.F == -1) break;
merge(R.F, R.S);
}
cout << res << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
