Submission #1133960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133960		OI_Account	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	4 ms	9792 KiB

joitter2

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

#define U first
#define V second

typedef long long ll;
typedef pair<int, int> edge;

const int N = 100'000;

int n, q, par[N + 10];
set<edge> eIn[N + 10], eOut[N + 10];
multiset<edge> all;
vector<edge> vec;
queue<edge> qu;
ll ans, cntIn[N + 10];

void init() {
    for (int i = 1; i <= n; i++)
        par[i] = -1;
}

int getPar(int u) {
    return (par[u] < 0? u: (par[u] = getPar(par[u])));
}

bool checkIn(int x, int u) {
    auto au = eIn[x].lower_bound({u, 0});
    return au != eIn[x].end() && au -> first == u;
}

void delIn(int x, edge e) {
    eIn[x].erase(e);
    if (!checkIn(x, e.U)) {
        cntIn[x]--;
        ans -= (ll) (-par[x]);
    }
}

void delOut(int x, edge e) {
    eOut[x].erase(e);
}

edge edgePar(edge e) {
    return {getPar(e.U), getPar(e.V)};
}

edge edgeParRev(edge e) {
    return {getPar(e.V), getPar(e.U)};
}

void delEdge(edge e) {
    delIn(getPar(e.V), e);
    delOut(getPar(e.U), e);
    all.erase(all.lower_bound(edgePar(e)));
}

void addIn(int x, edge e) {
    //cout << "here " << x << ' ' << e.U << ' ' << e.V << '\n';
    if (!checkIn(x, e.U)) {
        ans += (ll) (-par[x]);
        cntIn[x]++;
    }
    eIn[x].insert(e);
}

void addOut(int x, edge e) {
    eOut[x].insert(e);
}

bool isEdge(edge e) {
    auto au = all.find(e);
    return au != all.end();
}

void addEdge(edge e) {
    addIn(getPar(e.V), e);
    addOut(getPar(e.U), e);
    if (isEdge(edgeParRev(e)))
        qu.push(edge(e.V, e.U));
    all.insert(edgePar(e));
}

void delEdgeComp(int x) {
    vec.clear();
    for (auto au = eIn[x].begin(); au != eIn[x].end(); au++)
        vec.push_back(*au);
    for (auto au = eOut[x].begin(); au != eOut[x].end(); au++)
        vec.push_back(*au);
    for (auto e: vec)
        delEdge(e);
}

void addEdgeVec() {
    for (auto e: vec) {
        //cout << e.U << ' ' << e.V << endl;
        if (getPar(e.U) != getPar(e.V))
            addEdge(e);
    }
}

void merg(int u, int v) {
    //cout << "merg " << u << ' ' << v << ' ' << ans << endl;
    if ((u = getPar(u)) == (v = getPar(v)))
        return;
    if (par[v] < par[u])
        swap(u, v);
    delEdgeComp(v);
    //cout << "After del " << v << ": " << ans << endl;
    ans += (ll) par[u] * (ll) par[v] * 2ll;
    ans += (ll) (-par[v]) * cntIn[u];
    par[u] += par[v];
    par[v] = u;
    addEdgeVec();
    //cout << "now " << ans << endl;
    return;
}

void checkMerg() {
    while (!qu.empty()) {
        edge e = qu.front();
        qu.pop();
        merg(e.U, e.V);
    }
}

void query() {
    int u, v;
    cin >> u >> v;
    addEdge(edge(u, v));
    checkMerg();
    cout << ans << '\n';
}

void solve() {
    while (q--)
        query();
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    init();
    solve();
    return 0;
}

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