Submission #671945

#	Time	Username	Problem	Language	Result	Execution time	Memory
671945		ymm	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	1 ms	332 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;
	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(i != j);
	assert(node[i].rt == i);
	assert(node[j].rt == j);
	int szi = node[i].comp_nodes->size() + node[i].out_nodes->size();
	int szj = node[j].comp_nodes->size() + node[j].out_nodes->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);
	for (int k : *node[j].comp_nodes) {
		node[i].comp_nodes->push_back(k);
		node[k].rt = i;
	}
	delete(node[j].comp_nodes);
	ans += node[i].comp_nodes->size() * node[i].out_nodes->size();
	for (int k : *node[j].out_nodes)
		add(i, k);
	delete(node[j].out_nodes);
}

void add(int i, int j)
{
	i = node[i].rt;
	if (node[i].out_nodes->insert(j).second == false)
		return;
	ans += node[i].comp_nodes->size();
	j = node[j].rt;
	node[i].out_comp->insert(j);
	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});
	}
}

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:61:41: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   61 |   node[i].comp_nodes = new vector<int>({i});
      |                                         ^
joitter2.cpp:61:41: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
joitter2.cpp:62:37: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   62 |   node[i].out_nodes = new set<int>({i});
      |                                     ^
joitter2.cpp:62:37: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
joitter2.cpp:63:36: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   63 |   node[i].out_comp = new set<int>({i});
      |                                    ^
joitter2.cpp:63:36: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]

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