제출 #216560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216560		combi1k1	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	22 ms	19456 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];

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

    if (a == b) return;

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

    vector<Edge> rem;

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

        rem.pb(*it++);
    }
    if (rem.empty())    {
        E = Edge(x,y);

        if(!fr[a].count(E)) {
            fr[a].insert(E);
            to[b].insert(E);    ans += s[b];
        }
    }
    else    {
        pending.push(ii(a,b));

        for(Edge E : rem)   {
            fr[b].erase(E);
            to[a].erase(E); ans -= s[a];
        }
    }
}

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;   addEdge(x,y);

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

            Edge E(x,y);    E.a = 0;

            auto it = fr[x].lower_bound(E);

            assert(it == fr[x].end() || (*it).pb != y);

            pending.pop();

            if (x == y) continue;
            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),  addEdge(E.a,x);
            for(Edge E : fr[y]) to[E.pb].erase(E),  addEdge(E.a,E.pb),
                ans -= s[E.pb];

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

            ans += 1ll * s[x] * (s[x] - 1);
        }
//        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