Submission #211895

#	Time	Username	Problem	Language	Result	Execution time	Memory
211895		mieszko11b	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	778 ms	41720 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

using ll = long long;

int n, m;
int p[100007], ran[100007];
set<ii> GID[100007];
set<int> GO[100007];

ll res = 0;

void init() {
	for(int i = 1 ; i <= n ; i++) {
		p[i] = i;
		ran[i] = 1;
	}
}

int Find(int a) {
	if(p[a] == a)
		return a;
	return p[a] = Find(p[a]);
}

void remove_between(int a, int b) {
	set<ii>::iterator it;
	while((it = GID[b].lower_bound({a, 0})) != GID[b].end() && it->X == a) {
		//~ cout << "x" << endl;
		res -= ran[b];
		GID[b].erase(it);
		GO[a].erase(b);
	}	
}


void print_all() {
	cout << "res is " << res << endl;
	for(int i = 1 ; i <= n ; i++)
		cout << "rep of "<< i << " is "<<Find(i) << endl;
	for(int i = 1 ; i <= n ; i++) {
		if(i == Find(i)) {
			cout << "AAA " <<i << endl;
			cout << "OUT: ";
			for(int x : GO[i])
				cout << x << " ";
			cout << endl;
			cout << "IN: ";
			for(ii x : GID[i])
				cout << "(" << x.X << ","<<x.Y <<") ";
			cout << endl;
		}
	}
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	
	//~ cout << "Union " << a << " " << b << endl;
	//~ cout << "at the beginning:" << endl;
	//~ print_all();
	if(a == b)
		return ;
	
	if(ran[a] < ran[b])
		swap(a, b);

	remove_between(a, b);	
	//~ cout << "x" << endl;
	remove_between(b, a);
	
	//~ cout << "after edge removal:" << endl;
	//~ print_all();
	
	//~ cout << "x" << endl;
	
	vector<int> to_union;
	
	for(int x : GO[b]) {
		auto it = GID[x].lower_bound({b, 0});
		while((it = GID[x].lower_bound({b, 0})) != GID[x].end() && it->X == b) {
			auto p = *it;
			GID[x].erase(it);
			GID[x].insert({a, p.Y});
		}	
		GO[a].insert(x);
		if(GO[x].count(a))
			to_union.push_back(x);
	}
	GO[b].clear();
	
	res += (ll)ran[b] * GID[a].size();
	
	for(auto p : GID[b]) {
		GO[p.X].erase(b);
		GO[p.X].insert(a);
		if(!GID[a].count(p)) {
			res += ran[a];
			GID[a].insert(p);
		} else
			res -= ran[b];
		if(GO[a].count(p.X))
			to_union.push_back(p.X);
	}
	GID[b].clear();
	
	res -= (ll)ran[a] * (ran[a] - 1);
	res -= (ll)ran[b] * (ran[b] - 1);
	res += ll(ran[a] + ran[b]) * (ran[a] + ran[b] - 1);
	
	p[b] = a;
	ran[a] += ran[b];
	
	for(int x : to_union)
		Union(a, x);
}

void add_edge(int a, int b) {
	int wa = a;
	a = Find(a);
	b = Find(b);
	
	if(a == b)
		return ;
		
	if(!GID[b].count({a, wa})) {
		res += ran[b];
		GID[b].insert({a, wa});
		GO[a].insert(b);
	}
	
	if(GO[a].count(b) && GO[b].count(a))
		Union(a, b);
}


int main() {
	scanf("%d%d", &n, &m);
	init();
	for(int i = 0 ; i < m ; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add_edge(a, b);
		printf("%lld\n", res);
		//~ print_all();
	}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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