Submission #939370

#	Time	Username	Problem	Language	Result	Execution time	Memory
939370		pcc	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	3 ms	9820 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,b});
	in[rb].insert({ra,a});
	toaru[pii(ra,rb)]++;
	ans += sz[rb];
	return;
}

void combine(int a,int b){
	int ra = root(a),rb = root(b);
	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;
		}
		auto src = out[rt].lower_bound({ra,-1})->sc;
		out[rt].erase(out[rt].find(pii(ra,src)));
		out[rt].insert({rb,src});
		toaru[pii(rt,rb)]++;
		toaru[pii(rt,ra)]--;
		in[rb].insert({rt,now});
	}
	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(in[rt].find(pii(ra,src)));
		in[rt].insert({rb,src});
		toaru[pii(ra,rt)]--;
		toaru[pii(rb,rt)]++;
		out[rb].insert({rt,now});
	}
	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 combine(a,b);
}

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(int, int)':
joitter2.cpp:47:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |   auto [rt,now] = *in[ra].begin();
      |        ^
joitter2.cpp:61:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto [rt,now] = *out[ra].begin();
      |        ^

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