Submission #445316

#	Time	Username	Problem	Language	Result	Execution time	Memory
445316		ics0503	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	17 ms	25804 KiB

joitter2

#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];
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(s) != 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];
				}
				for (long long nxt : redge[x]) {
					long long pnxt = find(nxt);
					if (pnxt == ps) ans -= rsz[pe];
				}
				L[ps].push_back(pe);
				if(ar[ps].find(x)!=ar[ps].end()) ar[ps].erase(x);
			}
			ans += rsz[pe] * ar[ps].size();
			for (auto x : ar[pe]) {
				if (ar[ps].find(x) != ar[ps].end()) ans -= rsz[ps] + 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(e);
				sz[ps]++; sz[pe]++;
				ans += rsz[pe];
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83