Submission #445339

#	Time	Username	Problem	Language	Result	Execution time	Memory
445339		ics0503	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	1 / 100	5054 ms	31904 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], aar[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;
set<int>LL;
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]) {
		int ff = 1;
		for (long long nxt : edge[x]) {
			long long pnxt = find(nxt);
			if (pnxt == ps) {
				if(ff)ans -= rsz[ps];
				ff = 0;
			}
			else {
				if (pnxt != pe) {
					if (aar[pnxt].find(pe) != aar[pnxt].end())
						int sp = 1;
					aar[pnxt].erase(pe);
					aar[pnxt].insert(ps);
				}
			}
		}
		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 {
				if (pnxt != pe) {
					if (a[pnxt].find(pe) == a[pnxt].end())
						int sp = 1;
					a[pnxt].erase(pe);
					a[pnxt].insert(ps);
				}
			}
		}
		L[ps].push_back(x);
		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 : a[pe]) if (aar[ps].find(x) != aar[ps].end())LL.insert(x);
	for (auto x : aar[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);
	for (auto x : aar[pe]) aar[ps].insert(x);
	a[ps].erase(ps); aar[ps].erase(ps);
	par[pe] = ps;
	rsz[ps] += rsz[pe];
	sz[ps] += sz[pe];
	ans += rsz[ps] * (rsz[ps] - 1);
	if (LL.size() > 0) {
		auto now = *LL.begin();
		LL.erase(now);
		un(ps, now);
	}
}
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);

		{
			int x, y;
			for (x = 1; x <= n; x++) {
				if (par[x] != x)continue;
				for (y = 1; y <= n; y++) {
					if (x == y)continue;
					if (par[y] != y)continue;
					if (i == 96 && x == 46 && y==14)
						int sp = 1;
					if (a[x].find(y) != a[x].end() && aar[y].find(x) == aar[y].end()) {
						printf("!!fk\n%lld %d %d\n", i, x, y);
					}
					if (a[x].find(y) == a[x].end() && aar[y].find(x) != aar[y].end()) {
						printf("!!fk\n%lld %d %d\n", i, x, y);
					}
				}
			}
		}
		if (ps == pe) { printf("%lld\n", ans); continue; }
		if (a[pe].find(ps) != a[pe].end()) {
			un(s, e);
		}
		else {
			edge[s].insert(e); redge[e].insert(s);
			a[ps].insert(pe);
			aar[pe].insert(ps);
			if (ar[pe].find(s) == ar[pe].end()) {
				ar[pe].insert(s);
				sz[ps]++; sz[pe]++;
				ans += rsz[pe];
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void un(int, int)':
joitter2.cpp:33:11: warning: unused variable 'sp' [-Wunused-variable]
   33 |       int sp = 1;
      |           ^~
joitter2.cpp:50:11: warning: unused variable 'sp' [-Wunused-variable]
   50 |       int sp = 1;
      |           ^~
joitter2.cpp: In function 'int main()':
joitter2.cpp:103:11: warning: unused variable 'sp' [-Wunused-variable]
  103 |       int sp = 1;
      |           ^~
joitter2.cpp:89:15: warning: unused variable 'j' [-Wunused-variable]
   89 |  long long i, j;
      |               ^
joitter2.cpp:88:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  long long n, m; scanf("%lld%lld", &n, &m);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~
joitter2.cpp:92:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   long long s, e; scanf("%lld%lld", &s, &e);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83