Submission #1309030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309030		nanaseyuzuki	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	612 ms	144128 KiB

joitter2

#include <bits/stdc++.h>
// Kazusa_Megumi
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, m, par[mn], ans = 0;
// child[i] : các đỉnh cùng tplt với i
// in[i] : các đỉnh có cạnh nối đến tplt của i
// out[i] : các đỉnh có cạnh nối từ tplt của i
// direct[i] : các đỉnh có cạnh nối trực tiếp đến tplt của i
set <int> child[mn], in[mn], out[mn], direct[mn];
queue <pii> q;

void init(){
	for(int i = 1; i <= n; i++){
		par[i] = i;
		child[i].insert(i);
	}
}

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

int get_sz(int u){
	return (int)(child[u].size() + in[u].size() + out[u].size() + direct[u].size());
}

int get_ans(int u){
	int sz_in = direct[u].size(), sz_full = child[u].size();
	return sz_full * (sz_full - 1) + sz_in * sz_full;
}

void join(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return;

	if(get_sz(u) < get_sz(v)) swap(u, v);
	ans -= get_ans(u) + get_ans(v);
	par[v] = u;

	in[u].erase(v); out[v].erase(u);
	in[v].erase(u); out[u].erase(v);
 	
 	for(auto i : child[v]){
 		child[u].insert(i);
 		if(direct[u].count(i)) direct[u].erase(i);
 	}

 	for(auto i : in[v]){
 		i = find(i);

 		out[i].erase(v);
 		out[i].insert(u);

 		if(!out[u].count(i)) in[u].insert(i);
 		else{
 			out[u].erase(i);
 			q.push({u, i});
 		}
 	}

 	for(auto i : out[v]){
 		i = find(i);

 		in[i].erase(v);
 		in[i].insert(u);

 		if(!in[u].count(i)) out[u].insert(i);
 		else{
 			in[u].erase(i);
 			q.push({u, i});
 		}
 	}

 	for(auto i : direct[v]){
 		int ri = find(i);
 		if(ri == u) continue;
 		if(!out[u].count(ri)) direct[u].insert(i);
 		else direct[u].erase(i);
 	}

 	in[v].clear(), out[v].clear(), direct[v].clear(), child[v].clear();
 	ans += get_ans(u);
}

void solve() {
    cin >> n >> m;
    init();
    for(int i = 1; i <= m; i++){
    	int u, v; cin >> u >> v;
    	int ru = find(u), rv = find(v);
    	ans -= get_ans(rv);
    	if(ru != rv){
    		in[rv].insert(ru);
    		out[ru].insert(rv);
    		direct[rv].insert(u);
    		if(in[ru].count(rv)) q.push({ru, rv});
    	}
    	ans += get_ans(rv);

    	while(q.size()){
    		auto [x, y] = q.front();
    		q.pop(); join(x, y);
    	}
    	cout << ans << '\n';
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

joitter2.cpp:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main() {
      | ^~~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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