Submission #1193341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193341		farica	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	552 ms	65556 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
 
const int MOD = 1e9 + 7;
 
template<ll mod>
struct modnum {
	static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
 
	using S = conditional_t<is_big_mod, ll, int>;
	using L = conditional_t<is_big_mod, __int128, ll>;
 
	S x;
 
	modnum() : x(0) {}
	modnum(ll _x) {
		_x %= static_cast<ll>(mod);
		if (_x < 0) { _x += mod; }
		x = _x;
	}
 
	modnum pow(ll n) const {
		modnum res = 1;
		modnum cur = *this;
		while (n > 0) {
			if (n & 1) res *= cur;
			cur *= cur;
						n /= 2;
		}
		return res;
	}
	modnum inv() const { return (*this).pow(mod-2); }
 
	modnum& operator+=(const modnum& a){
		x += a.x;
		if (x >= mod) x -= mod;
		return *this;
	}
	modnum& operator-=(const modnum& a){
		if (x < a.x) x += mod;
		x -= a.x;
		return *this;
	}
	modnum& operator*=(const modnum& a){
		x = static_cast<L>(x) * a.x % mod;
		return *this;
	}
	modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
 
	friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
	friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
	friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
	friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
 
	friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
	friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
	friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
 
	friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
	friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};
 
using mint = modnum<MOD>;
 
template <class T> struct SegTree{
	vector<T> seg;
	int n;
	const T ID = 0;
 
	T cmb(T a, T b){
		return max(a,b);
	}
 
	SegTree(int _n){
		n = 1;
		while (n < _n) n *= 2;
		seg.assign(2 * n + 1, ID);
	}
 
	void set(int pos, T val){
		seg[pos + n] = val;
	}
 
	void build(){
		for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]);
	}
 
	void upd(int v, int tl, int tr, int pos, T val){
		if (tl == tr){
			seg[v] = val;
		} else {
			int tm = (tl + tr) / 2;
			if (pos <= tm) upd(2 * v, tl, tm, pos, val);
			else upd(2 * v + 1, tm + 1, tr, pos, val);
			seg[v] = cmb(seg[2 * v], seg[2 * v + 1]);
		}
	}
 
	void upd(int pos, T val){
		upd(1, 0, n - 1, pos, val);
			}
 
	T query(int v, int tl, int tr, int l, int r){
		if (l > r) return ID;
		if (l == tl && r == tr) return seg[v];
		int tm = (tl + tr) / 2;
		T res = query(2 * v, tl, tm, l, min(tm, r));
		res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
		return res;
	}
 
	T query(int l, int r){
		return query(1, 0, n - 1, l, r);
	}
};
 
struct DSU{
	vector<int> p, sz, used, mn, mx;
 
	DSU(int n){
		p.assign(n, 0);
		sz.assign(n, 1);
		used.assign(n, 0);
		mx.assign(n, 0);
		mn.assign(n, 0);
 
		for (int i = 0; i < n; i++) p[i] = i;
	}
 
	int find(int u){
		if (p[u] == u) return u;
		p[u] = find(p[u]);
		return p[u];
	}
		void unite(int u, int v){
		u = find(u);
		v = find(v);
		if (u == v) return;
 
		if (sz[u] < sz[v]) swap(u, v);
		p[v] = u;
		sz[u] += sz[v];
		used[u] += used[v];
		mn[u] = min(mn[u], mn[v]);
		mx[u] = max(mx[u], mx[v]);
	}
 
	bool same(int u, int v){
		return find(u) == find(v);
	}
 
	int size(int u){
		u = find(u);
		return sz[u];
	}
};

const int N = 100001;

struct BIT {
  int b[N], n;
 
  void init(int _n) {
    n = _n;
    for(int i = 0 ; i <= n ; ++i) b[i] = 0;
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  int query(int x) {
    int ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
} bit;

int prnt[N];
ll sz[N], ans = 0;
set<int>child[N], in[N], ot[N];
queue<pi>to_merge;

void insert_weak(int A, int B) {
	ot[A].insert(B);
	in[B].insert(A);
	if(ot[B].count(A)) to_merge.push({A,B});
}

int find(int A) { return prnt[A] = (prnt[A] == A ? A : find(prnt[A])); }

int dsu_size(int A) { return (int)in[A].size() + (int)ot[A].size() + (int)child[A].size(); }

void unite(int A, int B) {
	if(A==B) return;
	if(dsu_size(A) < dsu_size(B)) swap(A,B);
	ans += sz[B] * child[A].size() + sz[A] * child[B].size();
	prnt[B] = A;
	sz[A] += sz[B];
	for(int i: child[B]) {
		if(child[A].count(i)) ans -= sz[A];
		else child[A].insert(i);
	}
	ot[A].erase(B), in[A].erase(B);
	ot[B].erase(A), in[B].erase(A);
	for(int i: ot[B]) {
		in[i].erase(B);
		insert_weak(A, i);
	}
	for(int i: in[B]) {
		ot[i].erase(B);
		insert_weak(i, A);
	}
}
 
void solve() {
	int n, m;
	cin >> n >> m;
	for(int i=0; i<n; ++i) {
		sz[i] = 1;
		prnt[i] = i;
		child[i].insert(i);
	}
	while(m--) {
		int A, B;
		cin >> A >> B;
		--A, --B;
		B = find(B);
		if(find(A) != B && !child[B].count(A)) {
			child[B].insert(A);
			ans += sz[B];
			
			A = find(A);
			insert_weak(A,B);
			while(!to_merge.empty()) {
				tie(A,B) = to_merge.front();
				to_merge.pop();
				unite(find(A), find(B));
			}
		}
		cout << ans << '\n';
	}
}
 
int main(){
	//freopen("262144.in", "r", stdin);
	//freopen("262144.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 	
 
	int t = 1;
	while (t--) solve();
}

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