Submission #939465

#	Time	Username	Problem	Language	Result	Execution time	Memory
939465		pcc	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1232 ms	82260 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
int N,M;
ll ans = 0;
int dsu[mxn],sz[mxn];
set<pii> in[mxn],out[mxn];
map<pii,int> toaru;

int root(int k){
	return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}

void init(){
	for(int i = 1;i<=N;i++){
		dsu[i] = i;
		sz[i] = 1;
	}
	ans = 0;
	return;
}
void add_edge(int a,int b){
	int ra = root(a),rb = root(b);
	out[ra].insert({rb,a});
	in[rb].insert({ra,a});
	toaru[pii(ra,rb)]++;
	ans += sz[rb];
	return;
}

vector<pii> v;

void combine(){
	auto [a,b] = v.back();
	v.pop_back();
	//cerr<<"COMBINE:"<<a<<','<<b<<endl;
	int ra = root(a),rb = root(b);
	if(ra == rb)return;
	toaru.erase(pii(rb,ra));
	if(in[ra].size()+out[ra].size()>in[rb].size()+out[rb].size())swap(ra,rb);
	//cerr<<"ans:"<<ans<<endl;
	ans = ans-1ll*sz[ra]*in[ra].size()-1ll*sz[rb]*in[rb].size();
	//cerr<<"ans:"<<ans<<endl;
	while(!in[ra].empty()){
		auto [rt,now] = *in[ra].begin();
		in[ra].erase(in[ra].begin());
		//assert(rt != ra);
		if(rt == rb){
			continue;
		}
		out[rt].erase(pii(ra,now));
		out[rt].insert({rb,now});
		toaru[pii(rt,rb)]++;
		toaru[pii(rt,ra)]--;
		in[rb].insert({rt,now});
		auto it = in[rt].lower_bound({rb,-1});
		if(it != in[rt].end()&&it->fs == rb)v.emplace_back(rb,rt);
	}
	while(!out[ra].empty()){
		auto [rt,now] = *out[ra].begin();
		out[ra].erase(out[ra].begin());
		//assert(rt != ra);
		if(rt == rb){
			continue;
		}
		auto src = in[rt].lower_bound({ra,-1})->sc;
		in[rt].erase(pii(ra,now));
		in[rt].insert(pii(rb,now));
		toaru[pii(ra,rt)]--;
		toaru[pii(rb,rt)]++;
		out[rb].insert({rt,now});
		auto it = out[rt].lower_bound({rb,-1});
		if(it != out[rt].end()&&it->fs == rb)v.emplace_back(rb,rt);
	}
	out[rb].erase(out[rb].lower_bound({ra,-1}),out[rb].lower_bound({ra+1,-1}));
	in[rb].erase(in[rb].lower_bound({ra,-1}),in[rb].lower_bound({ra+1,-1}));
	//cerr<<a<<' '<<b<<":"<<ra<<' '<<rb<<endl;
	//cerr<<"in[rb]:";for(auto &i:in[rb])cerr<<i.fs<<','<<i.sc<<' ';cerr<<endl;
	//cerr<<"out[rb]:";for(auto &i:out[rb])cerr<<i.fs<<','<<i.sc<<' ';cerr<<endl;
	ans += 1ll*(sz[ra]+sz[rb])*in[rb].size();
	//cerr<<"ans:"<<ans<<endl;
	ans += 2ll*sz[ra]*sz[rb];
	dsu[ra] = rb;
	sz[rb] += sz[ra];
	return;
}

inline void calc(int a,int b){
	int rb = root(b),ra = root(a);
	if(in[rb].find(pii(ra,a)) != in[rb].end())return;
	else if(ra == rb)return;
	if(!toaru[pii(rb,ra)])add_edge(a,b);
	else v.push_back({a,b});
	while(!v.empty())combine();
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	init();
	for(int i = 1;i<=M;i++){
		int a,b;
		cin>>a>>b;
		calc(a,b);
		cout<<ans<<'\n';
	}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void combine()':
joitter2.cpp:42:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |  auto [a,b] = v.back();
      |       ^
joitter2.cpp:53:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |   auto [rt,now] = *in[ra].begin();
      |        ^
joitter2.cpp:68:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   auto [rt,now] = *out[ra].begin();
      |        ^
joitter2.cpp:74:8: warning: unused variable 'src' [-Wunused-variable]
   74 |   auto src = in[rt].lower_bound({ra,-1})->sc;
      |        ^~~

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