제출 #445324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445324		ics0503	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	21 ms	31692 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;
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 {
				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 {
				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 (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);
	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);
				aar[pe].insert(ps);
				a[ps].insert(pe);
				sz[ps]++; sz[pe]++;
				ans += rsz[pe];
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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