Submission #211831

#	Time	Username	Problem	Language	Result	Execution time	Memory
211831		Akashi	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	9 ms	9728 KiB

joitter2

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

struct edge{
    int group, nod, cnt;
    bool operator < (const edge &aux)const{
        if(group != aux.group) return group < aux.group;
        if(nod != aux.nod) return nod < aux.nod;
        return cnt < aux.cnt;
    }
};

int n, m;
int TT[100001], SZ[100001];
long long Sol = 0;

set <edge> in[100001];
set <edge> out[100001];

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(find(x) == find(y)) return ;

    if(out[x].size() + in[x].size() < out[y].size() + in[y].size()) swap(x, y);

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

//    set <edge> :: iterator it = out[x].lower_bound({y, 0, 0});
//    set <edge> :: iterator aux;
//    while(it != out[x].end() && it->group == y){
//        Sol = Sol - 1LL * SZ[y] * ;
//        out[x].erase
//    }

    for(auto it : out[x]){
        int z = find(it.group);
        if(z == y || z == x) continue ;
        Sol = Sol + 1LL * SZ[y] * it.cnt * SZ[z];
    }

    int sz = in[x].size();
    for(auto it : out[y]){
        int z = find(it.group);
        if(z == y) continue ;
        if(z == x){
            set <edge> :: iterator it2 = in[x].lower_bound({y, 0, 0});
            in[x].erase(it2);
            --sz;
            Sol = Sol - 1LL * SZ[x] * it.cnt;
            continue ;
        }

        Sol = Sol + 1LL * SZ[x] * SZ[z] * it.cnt;
        set <edge> :: iterator it2 = out[x].lower_bound({z, 0, 0});
        if(it2 == out[x].end() || it2->group != z) out[x].insert({z, 0, it.cnt});
        else{
            int cnt = it2->cnt + it.cnt;
            out[x].erase(it2);
            out[x].insert({z, 0, cnt});
        }

        it2 = in[z].lower_bound({y, 0, 0});
        int nod = it2->nod, cnt = it2->cnt;
        in[z].erase(it2);
        in[z].insert({x, nod, cnt});

    }
    Sol = Sol + 1LL * SZ[y] * sz;

    for(auto it : in[y]){
        int z = find(it.group);
        if(z == y) continue ;
        if(z == x){
            set <edge> :: iterator it2 = out[x].lower_bound({y, 0, 0});
            out[x].erase(it2);
            Sol = Sol - 1LL * SZ[y] * it.cnt;
            continue ;
        }

        set <edge> :: iterator it2 = in[x].lower_bound({z, it.nod, 0});
        if(it2 == in[x].end() || it2->group != z || it2->nod != it.nod){
            in[x].insert({z, it.nod, it.cnt});
            Sol = Sol + SZ[x];
        }

        it2 = out[z].lower_bound({y, 0, 0});
        int cnt = it2->cnt;
        out[z].erase(it2);

        it2 = out[z].lower_bound({x, 0, 0});
        if(it2 != out[z].end()){
            cnt += it2->cnt;
            out[z].erase(it2);
        }

        out[z].insert({x, 0, cnt});
    }

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

    for(auto it : out[y]){
        int z = find(it.group);
        if(z == x) continue ;

        set <edge> :: iterator it2 = in[x].lower_bound({z, 0, 0});
        if(it2 != in[x].end() && it2->group == z){
            unite(x, z);
            x = find(x);
        }
    }

    for(auto it : in[y]){
        int z = find(it.group);
        if(z == x) continue ;

        set <edge> :: iterator it2 = out[x].lower_bound({z, 0, 0});
        if(it2 != out[x].end() && it2->group == z){
            unite(x, z);
            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;

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

        x = find(x); y = find(y);

        it = out[y].lower_bound({x, 0, 0});
        if(it != out[y].end() && it->group == x){
            unite(x, y);
        }
        else{
            it = in[y].lower_bound({x, fx, 0});
            if(it != in[y].end() && it->group == x && it->nod == fx){
                printf("%lld\n", Sol);
                continue ;
            }
            Sol += SZ[y];
            it = out[x].lower_bound({y, 0, 0});
            if(it != out[x].end() && it->group == y){
                int cnt = it->cnt + 1;
                out[x].erase(it);
                out[x].insert({y, 0, cnt});
            }
            else out[x].insert({y, 0, 1});

            in[y].insert({x, fx, 1});
        }

        printf("%lld\n", Sol);
    }



    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:137:19: warning: variable 'fy' set but not used [-Wunused-but-set-variable]
     int x, y, fx, fy;
                   ^~
joitter2.cpp:134: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:140: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: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83