제출 #228605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228605		anonymous	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	10 ms	9728 KiB

joitter2

#include <iostream>
#include <map>
#define MAXN 100005
#define LL long long
using namespace std;
int N,M;
map <int,int> adj[MAXN]; //cliques each node is adjacent to
LL Ans;

class DSU {
    int Set[MAXN][3]; //par, clique size, incoming edge num
    map <int,int> M[MAXN];
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;
        }

        Ans += ((LL) Set[v][1]) * ((LL) Set[v][1] - 1);
        Ans += ((LL) Set[v][1]) * ((LL) Set[v][2]);
    }
    int addedge(int from, int to) {
        int u = Find(from), v= Find(to);
        if (u == v || adj[from].find(v) != adj[from].end()) {return(-1);}
        M[v][u]++;
        Set[v][2]++;
        Ans += Set[v][1];
        if (M[u][v] > 0) {
            Merge(u,v);
            return(-1);
        } else {
            return(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);
        int res = UF.addedge(a,b);
        if (res != -1) {adj[a][res]=1;}
        printf("%lld\n",Ans);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'int main()':
joitter2.cpp:60: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:64: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