Submission #211837

#	Time	Username	Problem	Language	Result	Execution time	Memory
211837		theStaticMind	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1048 ms	68100 KiB

joitter2

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int ans = 0;

vector<int> no(100005);
vector<int> S(100005, 1);
unordered_set<int> data[100005], indeg[100005], outdeg[100005]; 
queue<ii> Q;

void upans(int x, int sign){
	ans += sign * ((sz(data[x]) - S[x]) * S[x] + S[x] * (S[x] - 1)); 
}

int find(int x){
	
	if(no[x] == x) return x;
	return no[x] = find(no[x]);

}

bool merge(int x, int y){
	
	x = find(x);
	y = find(y);

	if(x == y) return false;

	upans(x, -1);
	upans(y, -1);

	if(indeg[x].count(y)) indeg[x].erase(y);
	if(indeg[y].count(x)) indeg[y].erase(x);
	if(outdeg[x].count(y)) outdeg[x].erase(y);
	if(outdeg[y].count(x)) outdeg[y].erase(x);
	
	if(sz(indeg[x]) + sz(outdeg[x]) < sz(indeg[y]) + sz(outdeg[y])) swap(x, y);
	
	for(auto p : outdeg[y]){
		if(indeg[x].count(p)) Q.push({x, p});
		indeg[p].erase(y);
		indeg[p].insert(x);
	}
	for(auto p : indeg[y]){
		if(outdeg[x].count(p)) Q.push({x, p});
		outdeg[p].erase(y);
		outdeg[p].insert(x);
	}

	if(outdeg[x].size() < outdeg[y].size()) swap(outdeg[x], outdeg[y]);
	if(indeg[x].size() < indeg[y].size()) swap(indeg[x], indeg[y]);
	if(data[x].size() < data[y].size()) swap(data[x], data[y]);
	
	for(auto p : data[y]) data[x].insert(p); data[y].clear();
	for(auto p : indeg[y]) indeg[x].insert(p); indeg[y].clear();
	for(auto p : outdeg[y]) outdeg[x].insert(p); outdeg[y].clear();
	
	no[y] = x;
	S[x] += S[y];

	upans(x, 1);

	return true;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	for(int i = 0; i < 100005; i++) no[i] = i, data[i].insert(i);
	
	int n, q;
	cin >> n >> q;
	
	while(q--){
		int x, y;
		cin >> x >> y;

		if(outdeg[find(y)].count(find(x))){
			Q.push({x, y});
			while(!Q.empty()){
				merge(Q.front().first, Q.front().second);
				Q.pop();
			}
			
		}
		else {
			y = find(y);
			upans(y, -1);
			data[y].insert(x);
			upans(y, 1);
			outdeg[find(x)].insert(y);
			indeg[y].insert(find(x));
		}
		cout << ans << '\n';
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'bool merge(long long int, long long int)':
joitter2.cpp:62:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto p : data[y]) data[x].insert(p); data[y].clear();
  ^~~
joitter2.cpp:62:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto p : data[y]) data[x].insert(p); data[y].clear();
                                           ^~~~
joitter2.cpp:63:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto p : indeg[y]) indeg[x].insert(p); indeg[y].clear();
  ^~~
joitter2.cpp:63:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto p : indeg[y]) indeg[x].insert(p); indeg[y].clear();
                                             ^~~~~
joitter2.cpp:64:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto p : outdeg[y]) outdeg[x].insert(p); outdeg[y].clear();
  ^~~
joitter2.cpp:64:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto p : outdeg[y]) outdeg[x].insert(p); outdeg[y].clear();
                                               ^~~~~~

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