Submission #573383

#	Time	Username	Problem	Language	Result	Execution time	Memory
573383		socpite	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	15 ms	30852 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{
    int root = -1;
    set<int> in;
    set<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;
    }
}

queue<pair<int, int>> edges;

void Union(int a, int b){
    if(up[a].in.size() + up[a].out.size() < up[b].in.size() + up[b].out.size())swap(a, b);
    ans+=1LL*up[a].root*(-up[a].root-1);
    ans+=1LL*up[b].root*(-up[b].root-1);
    ans -= 1LL*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].out.erase(b);
        edges.push({*it, a});
    }
    for(auto it = up[b].out.begin(); it != up[b].out.end(); it++){
        ans+=up[*it].root;
        up[*it].in.erase(b);
        edges.push({a, *it});
    }
    up[a].root+=up[b].root;
    up[b].root = a;
    ans-=1LL*up[a].root*(-up[a].root-1);
}

void add(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a==b)return;
    if(up[a].in.find(b) != up[a].in.end())Union(a, b);
    else{
        //cout << "sus" << endl;
        if(up[a].out.find(b) != up[a].out.end())return;
        ans -= up[b].root;
        up[a].out.insert(b);
        up[b].in.insert(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;
        edges.push({a, b});
        while(!edges.empty()){
            auto x = edges.front();
            edges.pop();
            add(x.f, x.s);
        }
        cout << ans << "\n";
    }
}

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