oj.uz

Submission #445320

# Submission time Handle Problem Language Result Execution time Memory
445320 2021-07-17T13:08:31 Z ics0503 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 18 ms 25976 KB 
#include<stdio.h>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
set<long long >edge[121212], redge[121212], ar[121212], a[121212];
vector<long long >L[121212];
long long par[121212], sz[121212], rsz[121212], ck[121212];
long long find(long long x) {
	if (par[x] == x)return x;
	return par[x] = find(par[x]);
}

long long ans = 0;
void un(int s, int e) {
	long long ps = find(s), pe = find(e);
	if (ps == pe)return;
	if (sz[ps] < sz[pe]) { swap(s, e), swap(ps, pe); }
	ans -= rsz[ps] * (rsz[ps] - 1);
	ans -= rsz[pe] * (rsz[pe] - 1);
	for (auto x : L[pe]) {
		for (long long nxt : edge[x]) {
			long long pnxt = find(nxt);
			if (pnxt == ps) {
				ans -= rsz[ps];
				break;
			}
		}
		for (long long nxt : redge[x]) {
			long long pnxt = find(nxt);
			if (pnxt == ps) {
				if (ck[nxt] == 0) {
					ans -= rsz[pe];
					ck[nxt] = 1;
				}
			}
			else {
				a[pnxt].erase(pe);
				a[pnxt].insert(ps);
			}
		}
		L[ps].push_back(pe);
		if (ar[ps].find(x) != ar[ps].end()) ar[ps].erase(x);
	}
	for (auto x : L[pe]) {
		for (long long nxt : redge[x]) {
			ck[nxt] = 0;
		}
	}
	ans += rsz[pe] * ar[ps].size();
	set<int>LL;
	for (auto x : a[pe]) {
		if (ar[ps].find(x) != ar[ps].end())LL.insert(x);
	}
	for (auto x : ar[pe]) {
		if (a[ps].find(x) != a[ps].end())LL.insert(x);
	}
	for (auto x : ar[pe]) {
		if (ar[ps].find(x) != ar[ps].end())ans -= rsz[pe];
		else if (find(x) != ps) {
			ans += rsz[ps];
			ar[ps].insert(x);
		}
	}
	for (auto x : a[pe])a[ps].insert(x);
	par[pe] = ps;
	rsz[ps] += rsz[pe];
	sz[ps] += sz[pe];
	ans += rsz[ps] * (rsz[ps] - 1);
	for (auto x : LL) {
		un(x, ps);
	}
}
int main() {
	long long n, m; scanf("%lld%lld", &n, &m);
	long long i, j;
	for (i = 1; i <= n; i++)par[i] = i, sz[i] = rsz[i] = 1, L[i].push_back(i);
	for (i = 0; i < m; i++) {
		long long s, e; scanf("%lld%lld", &s, &e);
		long long ps = find(s), pe = find(e);
		if (ps == pe) { printf("%lld\n", ans); continue; }
		if (a[pe].find(ps) != a[pe].end()) {
			un(s, e);
		}
		else {
			if (ar[pe].find(s) == ar[pe].end()) {
				edge[s].insert(e); redge[e].insert(s);
				ar[pe].insert(s);
				a[ps].insert(pe);
				sz[ps]++; sz[pe]++;
				ans += rsz[pe];
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:76:15: warning: unused variable 'j' [-Wunused-variable]
   76 |  long long i, j;
      |               ^
joitter2.cpp:75:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  long long n, m; scanf("%lld%lld", &n, &m);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~
joitter2.cpp:79:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   long long s, e; scanf("%lld%lld", &s, &e);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25804 KB Output is correct
2 Correct 16 ms 25804 KB Output is correct
3 Correct 16 ms 25804 KB Output is correct
4 Correct 17 ms 25904 KB Output is correct
5 Correct 17 ms 25804 KB Output is correct
6 Correct 16 ms 25888 KB Output is correct
7 Correct 17 ms 25976 KB Output is correct
8 Incorrect 18 ms 25916 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25804 KB Output is correct
2 Correct 16 ms 25804 KB Output is correct
3 Correct 16 ms 25804 KB Output is correct
4 Correct 17 ms 25904 KB Output is correct
5 Correct 17 ms 25804 KB Output is correct
6 Correct 16 ms 25888 KB Output is correct
7 Correct 17 ms 25976 KB Output is correct
8 Incorrect 18 ms 25916 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25804 KB Output is correct
2 Correct 16 ms 25804 KB Output is correct
3 Correct 16 ms 25804 KB Output is correct
4 Correct 17 ms 25904 KB Output is correct
5 Correct 17 ms 25804 KB Output is correct
6 Correct 16 ms 25888 KB Output is correct
7 Correct 17 ms 25976 KB Output is correct
8 Incorrect 18 ms 25916 KB Output isn't correct
9 Halted 0 ms 0 KB -