제출 #233410

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

joitter2

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#define LL long long
#define MAXN 100005
using namespace std;
int N, M, ai, bi;
LL ans;
vector <pair<int,int> > S;
class DSU {
public:
    int Set[MAXN][2];
    LL Num[MAXN]; //contribution by each clique
    set<int> To[MAXN], From[MAXN]; //cliques that i follows, cliques that follows i
    set<int> Nodes[MAXN], InClique[MAXN]; //nodes coming into clique, nodes in clique

    void Init() {
        for (int i=1; i<=N; i++) {
            InClique[i].insert(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 eval(int p) {
        ans -= Num[p];
        Num[p] = ((LL) Set[p][1]) * ((LL) Set[p][1] - 1) + ((LL) Nodes[p].size()) * ((LL) Set[p][1]);
        ans += Num[p];
    }

    void Union(int x, int y) { //clique ids
        x = Find(x), y = Find(y);
        if (x == y) {return;}
        if (Set[x][1] > Set[y][1]) {swap(x,y);}
        //printf("Union %d into %d\n",x,y);
        ans -= Num[x];
        for (int v: To[x]) {
            From[v].erase(x);
            if (v == y) {continue;}
            From[v].insert(y);
            To[y].insert(v);
            if (From[y].find(v) != From[y].end()) {
                S.push_back({y,v});
            }
        }
        for (int v: From[x]) {
            To[v].erase(x);
            if (v == y) {continue;}
            To[v].insert(y);
            From[y].insert(v);
            if (To[y].find(v) != To[y].end()) {
                S.push_back({y,v});
            }
        }
        for (int v: Nodes[x]) {
            if (InClique[y].find(v) != InClique[y].end()) {continue;}
            Nodes[y].insert(v);
        }
        for (int v: InClique[x]) {
            if (Nodes[y].find(v) != Nodes[y].end()) {
                Nodes[y].erase(v);
            }
            InClique[y].insert(v);
        }
        Set[y][1] = InClique[y].size();
        Set[x][0] = y;
        eval(y);
       // printf("DEBUG %d %d\n", Set[y][1], Nodes[y].size());
    }

    void addEdge(int x, int y) {
        int p1 = Find(x), p2 = Find(y);
        //printf("Add edge %d %d %d %d\n",x,y,p1,p2);
        if (Nodes[p2].find(x) != Nodes[p2].end() || p1 == p2) {
            return; //edge already exists or in same clique
        } else {
            To[p1].insert(p2);
            From[p2].insert(p1);
            Nodes[p2].insert(x);
            if (To[p2].find(p1) != To[p2].end()) {
                S.push_back({p1,p2});
            }
            eval(p1), eval(p2);
        }
    }
} DSU;

int main() {
    //freopen("joitterin.txt","r",stdin);
    scanf("%d %d",&N,&M);
    DSU.Init();
    for (int i=1; i<=M; i++) {
        scanf("%d %d",&ai,&bi);
        DSU.addEdge(ai, bi);
        while (S.size()) {
            int x = S.back().first, y = S.back().second;
            S.pop_back();
            DSU.Union(x,y);
        }
        printf("%lld\n", ans);
    }
}

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

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

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