Submission #769073

#	Time	Username	Problem	Language	Result	Execution time	Memory
769073		minhcool	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	27 ms	47228 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;

set<int> to[N];// to includes all nodes that are inside to
int rt[N], sz[N];

int answer;

int root(int x){
    return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

void merge(int x, int y){
    x = root(x), y = root(y);
    if(x == y) return;
    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);
    to[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);
	}
	for(int i = 1; i <= m; i++){
	    int x, y, yy;
	    cin >> x >> y;
	    yy = y;
	    y = root(y);
	    if(to[y].find(x) == to[y].end()){
	        to[y].insert(x);
	        answer += sz[y];
	    }
	    if(edges.find({yy, x}) != edges.end()) merge(x, yy);
	    edges.insert({x, yy});
	    cout << answer << "\n";
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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