Submission #216569

#	Time	Username	Problem	Language	Result	Execution time	Memory
216569		combi1k1	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	17 / 100	5078 ms	59112 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];
unordered_map<int,int>  cnt[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);

    if (it == fr[b].end() || (*it).pb != a) {
        E = Edge(x,y);

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

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);

            pending.pop();

            if (x == y) continue;

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

            vector<Edge> remA;
            vector<Edge> remB;

            for(auto it = fr[x].lower_bound(E) ; it != fr[x].end() && (*it).pb == y ; remA.pb(*it++));
            for(auto it = fr[y].lower_bound(F) ; it != fr[y].end() && (*it).pb == x ; remB.pb(*it++));

            for(Edge E : remA)  fr[x].erase(E), to[y].erase(E);
            for(Edge E : remB)  fr[y].erase(E), to[x].erase(E);

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

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

            ans += 2ll * s[x] * s[y];

            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();
        }
//        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: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 0 / 83