oj.uz

Submission #630332

# Submission time Handle Problem Language Result Execution time Memory
630332 2022-08-16T08:03:30 Z pooyashams Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 1 ms 340 KB 
#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 = 4096;

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;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -