Submission #573446

#	Time	Username	Problem	Language	Result	Execution time	Memory
573446		socpite	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	578 ms	64580 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 3e5+5;
const ll inf = 1e18;

int n, m;

ll ans = 0;

struct dsu{
    ll root = -1;
    set<pair<int, int>> in;
    set<pair<int, int>> out;
};

dsu up[maxn];

int Find(int x){
    if(up[x].root < 0)return x;
    else{
        up[x].root = Find(up[x].root);
        return up[x].root;
    }
}

struct edge{
    int a, b;
};

queue<edge> E;

void Union(int a, int b){
    auto it1 = up[b].out.lower_bound({a, 0});
    vector<pair<int, int>> tmp;
    for(it1; it1 != up[b].out.end(); it1++){
        if(it1->f != a)break;
        ans+=up[a].root;
        tmp.push_back(*it1);
    }
    for(auto x: tmp)up[b].out.erase(x);
    tmp.clear();
    for(auto it2 = up[a].in.lower_bound({Find(b), 0}); it2 != up[a].in.end(); it2++){
        if(it2->f != b)break;
        tmp.push_back(*it2);
    }
    for(auto x: tmp)up[a].in.erase(x);
    if(up[a].in.size() + up[a].out.size() < up[b].in.size() + up[b].out.size())swap(a, b);
    ans+=up[a].root*(-up[a].root-1);
    ans+=up[b].root*(-up[b].root-1);
    ans -= up[b].root*up[a].in.size();
    for(auto it = up[b].in.begin(); it != up[b].in.end(); it++){
        ans+=up[b].root;
        up[it->f].out.erase({b, it->s});
        E.push({it->s, a});
    }
    for(auto it = up[b].out.begin(); it != up[b].out.end(); it++){
        ans+=up[it->f].root;
        up[it->f].in.erase({b, it->s});
        E.push({it->s, it->f});
    }
    up[a].root+=up[b].root;
    up[b].root = a;
    ans-=up[a].root*(-up[a].root-1);
}

void add(edge x){
    int a = Find(x.a);
    int b = Find(x.b);
    if(a==b)return;
    auto it = up[a].in.lower_bound({b, 0});
    if(it != up[a].in.end() && it->f == b)Union(a, b);
    else{
        if(up[a].out.find({b, x.a}) != up[a].out.end())return;
        ans -= up[b].root;
        up[a].out.insert({b, x.a});
        up[b].in.insert({a, x.a});
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        E.push({a, b});
        while(!E.empty()){
            auto x = E.front();
            E.pop();
            add(x);
        }
        cout << ans << "\n";
    }
}

Compilation message (stderr)

joitter2.cpp: In function 'void Union(int, int)':
joitter2.cpp:41:9: warning: statement has no effect [-Wunused-value]
   41 |     for(it1; it1 != up[b].out.end(); it1++){
      |         ^~~

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