제출 #216459

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

joitter2

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 1e5 + 5;

typedef pair<int,int>   ii;

int p[N];
int s[N];

ll  ans = 0;

queue<ii>   pending;

int lead(int x) {
    return p[x] == x ? x : p[x] = lead(p[x]);
}

struct Edge {
    int pa, a;
    int pb;

    Edge(int _a = 0,int _b = 0) : pa(lead(_a)), a(_a), pb(lead(_b)) {}
};
bool operator < (const Edge&x,const Edge&y) {
    auto tmp1 = make_tuple(x.pa,x.pb,x.a);
    auto tmp2 = make_tuple(y.pa,y.pb,y.a);

    return  tmp1 < tmp2;
}
set<Edge> fr[N];
set<Edge> to[N];

bool Try(int x,int y)   {   //an egde directed from x to y
    int a = lead(x);
    int b = lead(y);

    Edge E(y,x);    E.a = 0;
    auto it = fr[b].lower_bound(E);
    bool ok = 0;

    while (it != fr[b].end())   {
        if ((*it).pa != b)  break;
        if ((*it).pb != a)  break;

        fr[b].erase(*it);
        to[a].erase(*it);   ans -= s[a];

        ok = 1;
        it++;
    }
    if (ok) {
        pending.push(ii(a,b));
        return  0;
    }
    if(!fr[a].count(Edge(x,y))) {
        fr[a].insert(Edge(x,y));
        to[b].insert(Edge(x,y));    ans += s[b];
    }

    return  1;
}
bool join(int x,int y)  {
    x = lead(x);
    y = lead(y);

    if (x == y) return  0;
    if (to[x].size() < to[y].size())
        swap(x,y);

    ans -= 1ll * s[x] * (s[x] - 1);
    ans -= 1ll * s[y] * (s[y] - 1);

    ans += 1ll * s[y] * sz(to[x]);
    ans -= 1ll * s[y] * sz(to[y]);

    p[y] = x;
    s[x] += s[y];

    for(Edge E : to[y]) fr[E.pa].erase(E),  Try(E.a,x);
    for(Edge E : fr[y]) to[E.pb].erase(E),  Try(E.a,E.pb),
        ans -= s[E.pb];

    fr[y].clear();
    to[y].clear();

    ans += 1ll * s[x] * (s[x] - 1);

    return  1;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;

    iota(p + 1,p + 1 + n,1);
    fill(s + 1,s + 1 + n,1);

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        int a = lead(x);
        int b = lead(y);

        if (a != b)
            Try(x,y);

        while (pending.size())  {
            int x = pending.front().X;
            int y = pending.front().Y;

            pending.pop();
            join(x,y);
        }
//        if (i == 2) {
//            for(int j = 1 ; j <= n ; ++j)   if (j == p[j])  {
//                cerr << "Info of " << j << "-th component:\n";
//                for(Edge e : fr[j]) cerr << e.a << "-" << e.b << "\n";
//                for(Edge e : to[j]) cerr << e.a << "-" << e.b << "\n";
//            }
//        }
        ll  ans = 0;

        for(int j = 1 ; j <= n ; ++j)
            if (j == p[j])
                ans += 1ll * s[j] * (s[j] - 1),
                ans += 1ll * s[j] * sz(to[j]);

        cout << ans << "\n";
    }
}

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