Submission #228606

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

joitter2

#include <iostream>
#include <map>
#include <set>
#define MAXN 100005
#define LL long long
using namespace std;
int N,M;
LL Ans;

class DSU {
    int Set[MAXN][3]; //par, clique size, incoming edge num
    map <int,int> M[MAXN];
    set <int> V[MAXN]; //nodes such that there is an OG edge going to clique
public:
    void init() {
        for (int i=1; i<=N; i++) {
            Set[i][0] = i, Set[i][1] = 1;
        }
    }
    int Find(int x) {
         if (Set[x][0] == x) {return(x);}
         return(Set[x][0] = Find(Set[x][0]));
    }
    void Merge(int x, int y) {
        int u = Find(x), v = Find(y);
        if (u == v) {return;}
        Ans -= ((LL) Set[u][1]) * ((LL) Set[u][1] - 1);
        Ans -= ((LL) Set[v][1]) * ((LL) Set[v][1] - 1);
        Ans -= ((LL) Set[u][2]) * ((LL) Set[u][1]);
        Ans -= ((LL) Set[v][2]) * ((LL) Set[v][1]);

        Set[v][2] -= M[v][u], Set[u][2] -= M[u][v];
        M[u].erase(v), M[v].erase(u);
        if (Set[u][1] > Set[v][1]) {swap(u,v);}
        Set[u][0] = v, Set[v][1] += Set[u][1];
        for (auto p: M[u]) {
            M[v][p.first] += p.second;
            Set[v][2] += p.second;
        }
        for (int p: V[u]) {
            V[v].insert(p);
        }

        Ans += ((LL) Set[v][1]) * ((LL) Set[v][1] - 1);
        Ans += ((LL) Set[v][1]) * ((LL) Set[v][2]);
    }
    void addedge(int from, int to) {
        int u = Find(from), v= Find(to);
        if (u == v || V[v].find(from) != V[v].end()) {return;}
        M[v][u]++;
        V[v].insert(from);
        Set[v][2]++;
        Ans += Set[v][1];
        if (M[u][v] > 0) {
            Merge(u,v);
        }
    }
} UF;

int main() {
    //freopen("joitterin.txt","r",stdin);
    scanf("%d %d",&N,&M);
    UF.init();
    for (int i=0; i<M; i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        UF.addedge(a,b);
        printf("%lld\n",Ans);
    }
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:62: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:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

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