제출 #884807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884807		mosaev	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	457 ms	49740 KiB

joitter2

//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4")
#include <complex>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define N ((ll)5e5+5)
#define M ((ll)1e9+7)
#define fi first
#define se second
#define bs (0b10000000000000000000)
#define inf ((ll)1e16)
struct dsu{
	queue<pair<ll, ll>> e;
	vector<ll> p, sz;
	ll ans;
	vector<set<ll>> in;
	vector<set<pair<ll, ll>>> out;
	void init(ll lsz) {p.resize(lsz+5), sz.resize(lsz+5), in.resize(lsz+5), out.resize(lsz+5);for(int i=1; i<=lsz; i++) p[i] = i, sz[i] = 1;}
	ll gpar(ll x) {return x==p[x] ? p[x]:p[x] = gpar(p[x]);}
	void merge(ll x, ll y){
		x=gpar(x), y=gpar(y);if(sz[x] < sz[y]) swap(x, y);
		for(auto z:out[y]){
			ans -= sz[z.fi];in[z.fi].erase(z.se);
			e.push({z.se, z.fi});
		}
		ans += sz[y]*sz[x]*2;
		ans += sz[y]*in[x].size();
		ll wef;
		for(auto z:in[y]){
			wef = gpar(z);out[wef].erase({y, z});ans-=sz[y];e.push({z, y});
		}
		in[y].clear(), out[y].clear();
		sz[x] += sz[y], p[y] = x;
	}
	ll add(ll x, ll y){
		e.push({x, y});while(e.size()){
			x=e.front().fi, y=e.front().se, e.pop();ll rx = gpar(x), ry = gpar(y);
			if(rx == ry || in[ry].find(x) != in[ry].end()) continue;
			auto f = out[ry].lower_bound({rx, 0});
			if(f==out[ry].end() || f->fi!=rx){
				ans += sz[ry];out[rx].insert({ry, x});in[ry].insert({x});
			}else{
				merge(rx, ry);
			}
		}
		return ans;
	}
};
ll n, m;
dsu ds;
int32_t main() {
#define int ll
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll a, b;cin >> n >> m;ds.init(n);
	for(int i=1; i<=m; i++) cin >> a >> b, cout << ds.add(a, b) << '\n';
}

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