oj.uz

Submission #269218

# Submission time Handle Problem Language Result Execution time Memory
269218 2020-08-17T05:47:40 Z 임성재(#5102) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 9 ms 9728 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;
const ll Mod = 1e9 + 7;

int n, m;
int a, b;
int p[100010];
ll sz[100010];
set<int> in[100010], out[100010];
ll ans;
vector<pii> q;

int Find(int a) {
	return a == p[a] ? a : Find(p[a]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if(a == b) return;

	p[b] = a;
	sz[a] += sz[b];
	sz[b] = 0;

	for(auto i : out[b]) {
		out[a].insert(i);
	}

	for(auto i : in[b]) {
		in[a].insert(i);
		//out[Find(i)].erase(b);
		out[Find(i)].insert(a);

		if(out[a].find(Find(i)) != out[a].end()) {
			q.eb(a, Find(i));
		}
	}

	vector<int> v;

	for(auto i : in[a]) {
		if(Find(i) == a) v.eb(i);
	}

	for(auto i : v) in[a].erase(i);
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=1; i<=n; i++) 
		p[i] = i, sz[i] = 1;

	for(int i=1; i<=m; i++) {
		cin >> a >> b;

		if(Find(a) == Find(b) || in[Find(b)].find(a) != in[Find(b)].end()) {
			cout << ans << "\n";
			continue;
		}

		in[Find(b)].insert(a);
		out[Find(a)].insert(Find(b));

		if(out[Find(b)].find(Find(a)) != out[Find(b)].end()) {
			q.eb(a, b);
		}

		while(q.size()) {
			auto x = q.back();
			q.pop_back();

			Union(x.fi, x.se);
		}

		ans = 0;
		for(int j=1; j<=n; j++) {
			if(j != Find(j)) continue;

			//cout << j << " " << sz[j] << " " << in[j].size() << "\n";

			ans += sz[j] * (sz[j] - 1);
			ans += sz[j] * in[j].size();
		}

		cout << ans << "\n";
	}

}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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