#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 2012;
int sz[maxn];
int root[maxn];
int get_root(int x)
{
if(root[x] == x) return x;
return get_root(root[x]);
}
inline bool mrg(int x, int y)
{
x = get_root(x);
y = get_root(y);
if(x == y) return false;
if(sz[x] < sz[y]) swap(x, y);
root[y] = x;
sz[x] += sz[y];
return true;
}
pii edgs[maxn];
bool vis[maxn][maxn];
inline int get_ans(int n)
{
int ans = 0;
for(int i = 0; i < n; i++)
{
if(root[i] == i)
{
ans += sz[i]*(sz[i]-1);
}
}
vector<pii> rms;
for(int i = 0; i < n; i++)
{
int x = edgs[i].X;
int y = get_root(edgs[i].Y);
if(get_root(x) == y) continue;
if(vis[x][y]) continue;
vis[x][y] = true;
rms.push_back(pii(x, y));
ans += sz[y];
//cerr << "adding sz " << x << " " << y << endl;
}
for(pii p: rms)
vis[p.X][p.Y] = false;
return ans;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
iota(root, root+n, 0);
fill(sz, sz+n, 1);
for(int i = 0; i < m; i++)
{
int x, y; cin >> x >> y;
x--; y--;
edgs[i] = pii(x, y);
//
int rx = get_root(x);
int ry = get_root(y);
if(rx != ry)
{
bool pos = false;
for(int j = 0; j < i; j++)
{
int a = edgs[j].X;
int b = edgs[j].Y;
if(get_root(a) == ry and get_root(b) == rx)
pos = true;
}
if(pos)
mrg(rx, ry);
}
//for(int j = 0; j < n; j++)
// cerr << get_root(j) << " ";
//cerr << endl;
//
cout << get_ans(i+1) << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
224 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
224 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
224 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
