Submission #834633

#	Time	Username	Problem	Language	Result	Execution time	Memory
834633		kingfran1907	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	9 ms	19028 KiB

joitter2

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;
const int maxn = 2e5+10;

int n, m;
int cale[maxn], siz[maxn];
llint sol = 0;
set< pair<int, int> > graph[maxn], graph2[maxn];

int fin(int x) {
	if (x == cale[x]) return x;
	return cale[x] = fin(cale[x]);
}

int get_size(int x) {
	return graph[x].size() + graph2[x].size();
}

void remove(int x, set< pair<int, int> > &s, bool flag = false) {
	auto iter = s.lower_bound({x, -1});
	while (iter != s.end() && iter->X == x) {
		//if (flag) printf("removing: %d %d (%d)\n", iter->X, iter->Y, siz[x]);
		sol -= siz[x] * flag;
		iter = s.erase(iter);
	}
}

void replace(int x, int y, set< pair<int, int> > &s, bool flag = false) {
	while (true) {
		auto iter = s.lower_bound({x, -1});
		if (iter == s.end() || iter->X != x) break;
		//if (flag) printf("replacing\n");
		if (!s.count({y, iter->Y})) {
			s.insert({y, iter->Y});
			sol += flag * siz[y];
		}
		s.erase(iter);
		sol -= flag * siz[x];
	}
}

void merge(int x, int y) {
	remove(x, graph[y], true);
	remove(y, graph[x], true);
	remove(x, graph2[y], false);
	remove(y, graph2[x], false);
	if (get_size(x) > get_size(y)) swap(x, y);
	
	//printf("merging: %d %d\n", x, y);
	cale[x] = y;
	sol -= (llint)siz[x] * (siz[x] - 1) + (llint)siz[y] * (siz[y] - 1);
	siz[y] += siz[x];
	sol += (llint)siz[y] * (siz[y] - 1);
	
	//printf("current: %lld\n", sol);
	int nex = -1;
	for (auto iter : graph[x]) {
		//printf("graph1: %d --> (%d %d)\n", x, iter.X, iter.Y);
		int tren = iter.X;
		int las = iter.Y;
		
		auto it = graph[tren].lower_bound({y, -1});
		if (it != graph[tren].end() && it->X == y) nex = tren;
		if (graph[y].count(iter) == 0) sol += siz[x];
		graph[y].insert(iter);
		sol -= siz[x];
		replace(x, y, graph2[tren]);
	}
	
	//printf("velicina: %d %d\n", siz[x], graph2[y].size());
	sol += (llint)siz[x] * graph2[y].size();
	for (auto iter : graph2[x]) {
		//printf("graph2: %d --> (%d %d)\n", x, iter.X, iter.Y);
		int tren = iter.X;
		int las = iter.Y;
		
		auto it = graph2[tren].lower_bound({y, -1});
		if (it != graph2[tren].end() && it->X == y) nex = tren;
		graph2[y].insert(iter);
		replace(x, y, graph[tren], true);
	}
	//printf("end: %lld\n", sol);
	if (nex != -1) merge(y, nex);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		cale[i] = i, siz[i] = 1;
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		
		int ca = a, cb = b;
		a = fin(a);
		b = fin(b);
		if (a == b) {
			auto iter = graph[b].lower_bound({a, -1});
			if (iter == graph[b].end() || iter->X != a) {
				if (!graph[a].count({b, ca})) {
					graph[a].insert({b, ca});
					sol += siz[b];
				}
				graph2[b].insert({a, 0});
			} else merge(a, b);
		}
		printf("%lld\n", sol);
	}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void merge(int, int)':
joitter2.cpp:64:7: warning: unused variable 'las' [-Wunused-variable]
   64 |   int las = iter.Y;
      |       ^~~
joitter2.cpp:79:7: warning: unused variable 'las' [-Wunused-variable]
   79 |   int las = iter.Y;
      |       ^~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:98:15: warning: unused variable 'cb' [-Wunused-variable]
   98 |   int ca = a, cb = b;
      |               ^~
joitter2.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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