Submission #671955

#	Time	Username	Problem	Language	Result	Execution time	Memory
671955		ymm	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1185 ms	91084 KiB

joitter2

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 300'010;

struct {
	set<int> *out_nodes, *out_comp;
	map<int, int> *in_comp;
	vector<int> *comp_nodes;
	int rt;
} node[N];

ll ans = 0;

void add(int i, int j);
void merge(int i, int j);

void merge(int i, int j)
{
	assert(node[i].rt == i);
	assert(node[j].rt == j);
	if (i == j)
		return;
	int szi = node[i].comp_nodes->size() + node[i].out_nodes->size() + node[i].in_comp->size();
	int szj = node[j].comp_nodes->size() + node[j].out_nodes->size() + node[i].in_comp->size();
	if (szi < szj)
		swap(i, j);
	ans -= node[i].comp_nodes->size() * node[i].out_nodes->size();
	ans -= node[j].comp_nodes->size() * node[j].out_nodes->size();
	delete(node[j].out_comp);
	node[j].out_comp = 0;
	for (int k : *node[j].comp_nodes) {
		node[i].comp_nodes->push_back(k);
		node[k].rt = i;
	}
	delete(node[j].comp_nodes);
	node[j].comp_nodes = 0;
	ans += node[i].comp_nodes->size() * node[i].out_nodes->size();
	for (auto [k, jj] : *node[j].in_comp) {
		if (node[k].out_comp == NULL)
			continue;
		add(k, jj);
	}
	delete(node[j].in_comp);
	node[j].in_comp = 0;
	for (int k : *node[j].out_nodes)
		add(i, k);
	delete(node[j].out_nodes);
	node[j].out_nodes = 0;
}

void add(int i, int j)
{
	i = node[i].rt;
	if (node[i].out_nodes->insert(j).second == true)
		ans += node[i].comp_nodes->size();
	int jj = j;
	j = node[j].rt;
	node[i].out_comp->insert(j);
	(*node[j].in_comp)[i] = jj;
	if (node[j].out_comp->count(i))
		merge(i, j);
}

void init(int n)
{
	Loop (i,0,n) {
		node[i].rt = i;
		node[i].comp_nodes = new vector<int>({i});
		node[i].out_nodes = new set<int>({i});
		node[i].out_comp = new set<int>({i});
		node[i].in_comp = new map<int, int>({{i, i}});
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	init(n);
	while (m--) {
		int i, j;
		cin >> i >> j;
		--i; --j;
		add(j, i);
		cout << ans << '\n';
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'void init(int)':
joitter2.cpp:74:41: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   74 |   node[i].comp_nodes = new vector<int>({i});
      |                                         ^
joitter2.cpp:74:41: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
joitter2.cpp:75:37: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   75 |   node[i].out_nodes = new set<int>({i});
      |                                     ^
joitter2.cpp:75:37: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
joitter2.cpp:76:36: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   76 |   node[i].out_comp = new set<int>({i});
      |                                    ^
joitter2.cpp:76:36: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]

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