Submission #212799

#	Time	Username	Problem	Language	Result	Execution time	Memory
212799		BThero	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1067 ms	64632 KiB

joitter2

#define DBG 1
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (DBG) cerr << #x << " = " << x << endl;

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)1e5 + 5;

set<int> in[MAXN], out[MAXN], inv[MAXN];
vector<int> ver[MAXN];
int par[MAXN];
pii Q[MAXN];
int n, m, t;
ll ans;

int getPar(int x) {
    if (x == par[x]) {
        return x;
    }
    
    return par[x] = getPar(par[x]);
}

ll f(int x) {
    return ver[x].size() * (ver[x].size() - 1ll + inv[x].size());
}

void uni(int a, int b) {
    a = getPar(a);
    b = getPar(b);
    
    if (a == b) {
        return;
    }
    
    ans -= f(b);
    ans -= f(a);
    
    if (inv[a].size() + ver[a].size() + in[a].size() + out[a].size() < inv[b].size() + ver[b].size() + in[b].size() + out[b].size()) {
        swap(a, b);
    }
    
    for (int x : inv[b]) {
        if (getPar(x) != a) {
            inv[a].insert(x);
        }
    }
    
    inv[b].clear();
    
    for (int x : ver[b]) {
        inv[a].erase(x);
        ver[a].pb(x);
    }
    
    in[a].erase(b);
    out[a].erase(b);
    in[b].erase(a);
    out[b].erase(a);
    
    for (int x : out[b]) {
        in[x].erase(b);
        in[x].insert(a);
        out[a].insert(x);
        
        if (in[a].find(x) != in[a].end()) {
            Q[t++] = mp(a, x);
        }
    }
    
    out[b].clear();
    
    for (int x : in[b]) {
        out[x].erase(b);
        out[x].insert(a);
        in[a].insert(x);
        
        if (out[a].find(x) != out[a].end()) {
            Q[t++] = mp(a, x);
        }
    }
    
    in[b].clear();
    par[b] = a;
    ans += f(a);
}

void push() {
    for (int i = 0; i < t; ++i) {
        uni(Q[i].fi, Q[i].se);
    }
}

void solve() {
	scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        ver[i].pb(i);
    }
    
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        v = getPar(v);
        
        if (getPar(u) != v) {
            ans -= f(v);
            inv[v].insert(u);
            u = getPar(u);
            out[u].insert(v);
            in[v].insert(u);
            ans += f(v);
            
            if (in[u].find(v) != in[u].end()) {
                t = 0;
                Q[t++] = mp(u, v);
                push();
            }
        }
        
        printf("%lld\n", ans);
    }
}

int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}

	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void solve()':
joitter2.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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