oj.uz

Submission #269161

# Submission time Handle Problem Language Result Execution time Memory
269161 2020-08-17T05:30:54 Z 임성재(#5102) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 8 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[300010];
int b[300010];
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);

	ans -= sz[a] * (sz[a] - 1) + sz[b] * (sz[b] - 1);
	ans -= sz[a] * in[a].size() + sz[b] * in[b].size();

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

	ans += sz[a] * (sz[a] - 1);

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

	for(auto i : in[b]) {
		in[a].insert(i);
		if(out[a].find(Find(i)) != out[a].end() && Find(i) != a) {
			//cout << a << "!!! " << Find(i) << endl;
			q.eb(a, Find(i));
		}
		else out[Find(i)].insert(a);
	}

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

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

	ans += sz[a] * in[a].size();
}

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[i] >> b[i];

		if(Find(a[i]) == Find(b[i])) {
			cout << ans << "\n";
			continue;
		}

		if(out[Find(b[i])].find(Find(a[i])) != out[Find(b[i])].end()) {
			q.eb(a[i], b[i]);
			
			while(q.size()) {
				auto x = q.back();
				q.pop_back();
				//cout << x.fi << "? " << x.se << endl;
				Union(x.fi, x.se);
			}
		}
		else {
			ans -= sz[Find(b[i])] * in[Find(b[i])].size();

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

			ans += sz[Find(b[i])] * in[Find(b[i])].size();
		}

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

}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Incorrect 7 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 8 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Incorrect 7 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 8 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Incorrect 7 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -