Submission #359857

#	Time	Username	Problem	Language	Result	Execution time	Memory
359857		soroush	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1561 ms	144152 KiB

joitter2

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n, k;
ll m = 0;
int par[maxn];
vector < pii > e[maxn];
set < int > out[maxn] , in[maxn] , rlin[maxn];
set < pii > rlo[maxn];

int getpar(int v){
	return((!par[v]) ? v : par[v] = getpar(par[v]));
}

int sz[maxn];

queue < pii > q;

#define siz(x) (ll)x.size()

void merge(int v , int u){
	if(e[v].size() < e[u].size())
		swap(u , v);
	m -= sz[u] * siz(rlin[u]);
	m += sz[u] * siz(rlin[v]);
	for(int x : rlin[u])
		rlo[getpar(x)].erase({u , x});
	for(auto x : rlo[u]){
		m -= sz[x.first];
		rlin[x.first].erase(x.second);
		if(x.first == v)
			m -= sz[u];
	}
	for(auto x : e[u])
		q.push(x);
	m += sz[v] * sz[u] * 2;
	sz[v] += sz[u];
	par[u] = v;
	out[u].clear();
	in[u].clear();
	e[u].clear();	
	rlo[u].clear();
	rlin[u].clear();
}

int32_t main(){
	migmig;
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++)sz[i] = 1;
	while(k--){
		int u , v;
		cin >> u >> v;
		q.push(pii(u , v));
		while(!q.empty()){
			int v = q.front().first , u = q.front().second;
			q.pop();
			if(getpar(v) == getpar(u))continue;
			int U = getpar(u) , V = getpar(v);
			if(out[U].count(V))
				merge(U , V);
			else{
				if(rlo[V].count(pii(U , v)))continue;
				e[V].pb({v , u}) , e[U].pb(pii(v , u));
				rlo[V].insert(pii(U , v));
				rlin[U].insert(v);
				out[V].insert(U);
				in[U].insert(V);
				m+=sz[U];
			}
		}
		cout << m << endl;
	}
	return(0);
}

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