Submission #211897

#	Time	Username	Problem	Language	Result	Execution time	Memory
211897		Akashi	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1349 ms	79352 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

int n, m;
int TT[100001], SZ[100001];
set <int> in[100001], out[100001], bridge[100001], elem[100001];

long long Sol = 0;
inline int find(int x){
    if(x != TT[x]) return (TT[x] = find(TT[x]));
    return x;
}

inline void unite(int x, int y){
    if(x == y) return ;
    if(elem[x].size() + in[x].size() + out[x].size() + bridge[x].size() < in[y].size() + out[y].size() + bridge[y].size() + elem[y].size()) swap(x, y);

    Sol += 2LL * SZ[x] * SZ[y];

    for(auto it : bridge[y]) if(elem[x].count(it)) Sol = Sol - SZ[y];
    for(auto it : elem[y]) if(bridge[x].count(it)) Sol = Sol - SZ[x];

    for(auto it : bridge[y]) if(!bridge[x].count(it) && !elem[x].count(it)) Sol = Sol + SZ[x];

    int nr = bridge[x].size();
    for(auto it : bridge[y]) if(bridge[x].count(it)) --nr;
    for(auto it : elem[y]) if(bridge[x].count(it)) --nr;
    Sol = Sol + 1LL * SZ[y] * nr;

    for(auto it : elem[y]){
        elem[x].insert(it);
        if(bridge[x].count(it)) bridge[x].erase(it);
    }

    for(auto it : bridge[y]) if(!elem[x].count(it)) bridge[x].insert(it);

    if(in[x].count(y)) in[x].erase(y);
    if(out[x].count(y)) out[x].erase(y);

    for(auto it : in[y]){
        if(it != x){
            in[x].insert(it);
            out[it].erase(y);
            out[it].insert(x);
        }
    }
    for(auto it : out[y]){
        if(it != x){
            out[x].insert(it);
            in[it].erase(y);
            in[it].insert(x);
        }
    }

    SZ[x] += SZ[y];
    TT[y] = x;

    for(auto it : in[y]){
        if(out[x].count(it)){
            unite(x, find(it));
            x = find(x);
        }
    }

    for(auto it : out[y]){
        if(in[x].count(it)){
            unite(x, find(it));
            x = find(x);
        }
    }
}

int main()
{
//    freopen("1.in", "r", stdin);
//    freopen("1.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; ++i){
        TT[i] = i, SZ[i] = 1;
        elem[i].insert(i);
    }

    int x, y, fx, fy;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &x, &y);
        fx = x; fy = y;
        x = find(x); y = find(y);
        if(x == y){
            printf("%lld\n", Sol);
            continue ;
        }

        if(!bridge[y].count(fx)){
            out[x].insert(y);
            in[y].insert(x);
            bridge[y].insert(fx);

            Sol += SZ[y];
            if(in[x].count(y)) unite(x, y);
        }
        printf("%lld\n", Sol);
    }

    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:84:19: warning: variable 'fy' set but not used [-Wunused-but-set-variable]
     int x, y, fx, fy;
                   ^~
joitter2.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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