Submission #1262774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262774		bot1132	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	18 ms	37960 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 77;
#define ll long long
int n,m,f[N],X[N],Y[N],t;
int F(int x) { return x == f[x] ? f[x] : f[x] = F(f[x]); }
set<int> a[N],b[N],u[N],c[N];
ll W,S;

ll Work(int i) {
    int _s = (int)u[i].size();
    return 1ll * _s * (_s - 1 + (int)c[i].size());
}

void Merge(int x,int y) {
    x = F(x);
    y = F(y);
    if (x == y)
        return;

    if (u[x].size() < u[y].size())
        swap(x,y);

    S -= Work(x) + Work(y);
    f[y] = x;

    for (int i : u[y]) { u[x].insert(i), c[x].erase(i); }
    for (int i : c[y]) {
        if (!u[x].count(i))
            c[x].insert(i);
    }
    for (int i : a[y]) {
        if (i != x)
            b[i].erase(y), b[i].insert(x);
        if (!u[x].count(i))
            a[x].insert(i);
        if (b[x].count(i))
            ++t, X[t] = x, Y[t] = i;
    }
    for (int i : b[y]) {
        if (i != x)
            a[i].erase(y), a[i].insert(x);
        if (!u[x].count(i))
            b[x].insert(i);
        if (a[x].count(i))
            ++t, X[t] = x,Y[t] = i;
    }
    a[y].clear(), b[y].clear(), c[y].clear();
    u[y].clear();
    S += Work(x);
}

int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) f[i] = i,u[i].insert(i);
    scanf("%d",&m);
    for (int x,y; m--; ) {
        scanf("%d%d",&x,&y);
        int _x = F(x), _y = F(y);
        if (_x == _y) {
            printf("%lld\n",W);
            continue;
        }
        if (a[_x].count(_y)) {
            Merge(x,y);
            while (t) {
                int _X = X[t],_Y = Y[t];
                Merge(_X,_Y);
                t--;
            }
        } else if (!c[_y].count(x)) {
            c[_y].insert(x);
            b[_x].insert(_y);
            a[_y].insert(_x);
            S += (int)u[_y].size();
        }
        W = max(W,S);
        printf("%lld\n",W);
    }
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
joitter2.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
joitter2.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

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