제출 #321990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321990		aZvezda	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	1 / 100	5098 ms	18412 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 1e5 + 10;

ll par[MAX_N], sz[MAX_N];
map<pair<ll, ll>, ll> cnt;
set<pair<int, int>> perr[MAX_N];
map<int, int> toClique[MAX_N];
ll ans, in[MAX_N];

int find(int x) {
	if(x == par[x]) {
		return x;
	} else {
		return par[x] = find(par[x]);
	}
}

void remove(int x, int y) {
	ll compx = find(x), compy = find(y);
	if(compx == compy) {return;}
	//cout << "Remove " << x << " " << y << " " << compx << " " << compy  << endl;
	cnt[{compx, compy}] --;
	perr[compx].erase({x, y});
	perr[compy].erase({x, y});
	if(toClique[x][compy] == 1) {
		ans -= sz[compy];
		in[compy] --;
	}
	toClique[x][compy] --;
} 

void add(int x, int y) {
	ll compx = find(x), compy = find(y);
	if(compx == compy) {return;}
	//cout << "Add " << x << " " << y << " " << compx << " " << compy  << endl;
	cnt[{compx, compy}] ++;
 	perr[compx].insert({x, y});
	perr[compy].insert({x, y});
	if(toClique[x][compy] == 0) {
		ans += sz[compy];
		in[compy] ++;
	} 
	toClique[x][compy] ++;
}

stack<pair<int, int> > st;

void merge(int x, int y) {
	ans -= (sz[x] * sz[x] - sz[x]);
	ans -= (sz[y] * sz[y] - sz[y]);
	if(perr[x].size() + sz[x] < perr[y].size() + sz[y]) {swap(x, y);}
	for(auto it : perr[y]) {
		remove(it.first, it.second);
		st.push(it);
	}
	ans += in[x] * sz[y];
	perr[y].clear();
	par[y] = x;
	sz[x] += sz[y]; 
	ans += (sz[x] * sz[x] - sz[x]);
}

void fixStack() {
	//cout << "Fixing" << endl;
	while(!st.empty()) {
		auto curr = st.top(); st.pop();
		//cout << curr << endl;
		if(cnt[{find(curr.second), find(curr.first)}] != 0) {
			//cout << "Have to merge" << curr << endl;
			merge(find(curr.first), find(curr.second));
		} else {
			add(curr.first, curr.second);
		}
	}	
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for(int i = 0; i < MAX_N; i ++) {par[i] = i; sz[i] = 1;}
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i ++) {
		int a, b;
		cin >> a >> b;
		st.push({a, b});
		fixStack();
		cout << ans << endl;
	}
	return 0;
}

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