Submission #216728

#	Time	Username	Problem	Language	Result	Execution time	Memory
216728		ainta	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	2257 ms	121324 KiB

joitter2

#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#define N_ 101000
using namespace std;
int n, m, UF[N_];
long long res, InD[N_];
map<int, int>Out[N_], In[N_];
vector<int>G[N_];
set<int>E[N_], F[N_];
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
void Merge(int a, int b) {
	if (Find(a) == Find(b))return;
	int pa = Find(a), pb = Find(b);

	int nd = InD[pa] + InD[pb] - Out[pb][pa] - Out[pa][pb];
	res += 1ll * (G[pa].size() + G[pb].size()) * nd + 1ll * G[pa].size()*G[pb].size() * 2;
	res -= 1ll * InD[pb] * G[pb].size();
	res -= 1ll * InD[pa] * G[pa].size();

	if (G[pa].size() + In[pa].size() + Out[pa].size() + F[pa].size() < G[pb].size() + In[pb].size() + Out[pb].size() + F[pb].size())swap(pa, pb);
	InD[pa] = nd;
	
	In[pb].erase(pa);
	Out[pb].erase(pa);

	set<int>TS;

	for (auto &t : In[pb]) {
		if (t.first != pa) {
			if (Out[pa].count(t.first))TS.insert(t.first);
			In[pa][t.first] += t.second;
			Out[t.first][pa] += t.second;
		}
	}
	for (auto &t : Out[pb]) {
		if (t.first != pa) {
			if (In[pa].count(t.first))TS.insert(t.first);
			Out[pa][t.first] += t.second;
			In[t.first][pa] += t.second;
		}
	}
	for (auto &t : G[pb]) {
		G[pa].push_back(t);
	}

	for (auto &t : F[pb]) {
		if (Find(t) == pa || Find(t) == pb)continue;
		if (E[t].find(pa) != E[t].end()) {
			int zz = Find(t);
			Out[zz][pa]--;
			In[pa][zz]--;
			res -= G[pa].size();
			InD[pa]--;
		}
		E[t].erase(pb);
		E[t].insert(pa);
		F[pa].insert(t);
	}

	In[pb].clear();
	Out[pb].clear();
	G[pb].clear();
	F[pb].clear();
	UF[pb] = pa;
	for (auto &t : TS) {
		Merge(pa, t);
	}
}
int main() {
	int i;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		UF[i] = i;
		G[i].push_back(i);
	}
	for (i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		int pa, pb;
		pa = Find(a), pb = Find(b);
		if (pa != pb) {
			if (Out[pb].count(pa)) {
				Merge(pa, pb);
			}
			else {
				if(E[a].find(pb) == E[a].end()){
					res += G[pb].size();
					Out[pa][pb]++;
					In[pb][pa]++;
					InD[pb]++;
					E[a].insert(pb);
					F[pb].insert(a);
				}
			}
		}
		printf("%lld\n", res);
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:77: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:84: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