Submission #444839

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

joitter2

#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
multiset<int>edge[121212],redge[121212];
long long par[121212], sz[121212];
int find(int x) {
	if (par[x] == x)return x;
	return par[x] = find(par[x]);
}
int main() {
	freopen("input.txt", "r", stdin);
	int n, m; scanf("%d%d", &n, &m);
	int i, j;
	for (i = 1; i <= n; i++)par[i] = i, sz[i] = 1;
	long long ans = 0;
	for (i = 0; i < m; i++) {
		int s, e; scanf("%d%d", &s, &e);
		int ps = find(s), pe = find(e);
		if (ps == pe)continue;
		if (redge[ps].find(pe) != redge[ps].end()) {
			ans -= sz[ps] * (sz[ps] - 1);
			ans -= sz[pe] * (sz[pe] - 1);
			
			if (edge[ps].size() + redge[ps].size() < edge[pe].size() + redge[pe].size()) {
				swap(ps, pe);
			}
			for (auto v : redge[pe]) {
				if (v == ps) { ans -= sz[pe]; continue; }
				edge[v].erase(edge[v].find(pe));
				edge[v].insert(ps);
				if (redge[ps].find(v) == redge[ps].end()) {
					ans -= sz[pe];
					ans += (sz[ps] + sz[pe]);
					redge[ps].insert(v);
				}
			}
			for (auto v : redge[ps]) {
				if (v == pe) { ans -= sz[ps]; continue; }
				if (redge[pe].find(v) == redge[pe].end()) {
					ans -= sz[ps];
					ans += (sz[ps] + sz[pe]);
				}
			}
			for (auto v : edge[pe]) {
				if (v == ps)continue;
				if (edge[ps].find(v) == edge[ps].end()) {
					edge[ps].insert(v);
					redge[v].erase(redge[v].find(pe));
					redge[v].insert(ps);
				}
			}
			edge[ps].erase(pe);
			sz[ps] += sz[pe];
			par[pe] = ps;
			ans += sz[ps] * (sz[ps] - 1);
		}
		else {
			edge[ps].insert(pe);
			redge[pe].insert(ps);
			ans += sz[pe];
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:14:9: warning: unused variable 'j' [-Wunused-variable]
   14 |  int i, j;
      |         ^
joitter2.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen("input.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:13:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  int n, m; scanf("%d%d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:18:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   int s, e; scanf("%d%d", &s, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~

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