Submission #769678

#	Time	Username	Problem	Language	Result	Execution time	Memory
769678		minhcool	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	2005 ms	364240 KiB

joitter2

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n, m;
set<ii> edges;
 
unordered_set<int> to[N], from[N];// to includes all nodes that are inside to
unordered_set<int> tocomp[N], fromcomp[N];
int rt[N], sz[N];
 
int answer;
 
int root(int x){
    return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

queue<ii> q;
 
void merge(int x, int y){
    x = root(x), y = root(y);
    if(x == y) return;
  //  cout << x << " " << y << "\n";
    if(sz[x] < sz[y]) swap(x, y);
    answer -= sz[x] * (to[x].size() - sz[x]);
    answer -= (sz[x] * (sz[x] - 1));
    answer -= sz[y] * (to[y].size() - sz[y]);
    answer -= (sz[y] * (sz[y] - 1));
    rt[y] = x;
    sz[x] += sz[y];
    //for(auto it : to[y]) to[x].insert(it);
    for(auto it : from[y]) from[x].insert(it);
    for(auto it : to[y]) to[x].insert(it);
    for(auto it : fromcomp[y]){
        fromcomp[x].insert(it);
        tocomp[it].insert(x);
    }
    for(auto it : tocomp[y]){
        tocomp[x].insert(it);
        fromcomp[it].insert(x);
    }
    for(auto it : tocomp[y]){
        //cout << it << "\n";
        if(tocomp[it].find(x) != tocomp[it].end()) q.push({x, it});
    }
    for(auto it : fromcomp[y]){
        //cout << it << "\n";
        if(fromcomp[it].find(x) != fromcomp[it].end()) q.push({x, it});
    }
    //for(auto it : tocomp[x]) cout << it << " ";
    //cout << "\n";
    //for(auto it : fromcomp[x]) cout << it << " ";
    //cout << "\n";
    //for(auto it : tocomp[5]) cout << it << " ";
    //cout <<"\n";
    from[y].clear();
    to[y].clear();
    tocomp[y].clear();
    fromcomp[y].clear();
    answer += sz[x] * (to[x].size() - sz[x]);
    answer += sz[x] * (sz[x] - 1);
}
 
#ifdef local
void process(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
	    rt[i] = i, sz[i] = 1, to[i].insert(i), from[i].insert(i), tocomp[i].insert(i), fromcomp[i].insert(i);
	}
	for(int i = 1; i <= m; i++){
	    int x, y;
	    cin >> x >> y;
	    int xx = root(x), yy = root(y);
	    if(xx != yy){
	        if(to[yy].find(x) == to[yy].end()){
	            to[yy].insert(x);
	            answer += sz[yy];
	        }
	        from[xx].insert(y);
	        fromcomp[xx].insert(yy);
	        tocomp[yy].insert(xx);
	        if(fromcomp[yy].find(xx) != fromcomp[yy].end()) q.push({xx, yy});
	    }
	    while(!q.empty()){
	        merge(q.front().fi, q.front().se);
	        q.pop();
	    }
	    //edges.insert({x, yy});
	    cout << answer << "\n";
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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