oj.uz

Submission #445318

# Submission time Handle Problem Language Result Execution time Memory
445318 2021-07-17T12:59:36 Z ics0503 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 17 ms 25892 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]);
}
int main() {
	long long n, m; scanf("%lld%lld", &n, &m);
	long long i, j;
	long long ans = 0;
	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()) {
			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();
			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);
		}
		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:15:15: warning: unused variable 'j' [-Wunused-variable]
   15 |  long long i, j;
      |               ^
joitter2.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  long long n, m; scanf("%lld%lld", &n, &m);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~
joitter2.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   long long s, e; scanf("%lld%lld", &s, &e);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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