Submission #679461

#	Time	Username	Problem	Language	Result	Execution time	Memory
679461		qwerasdfzxcl	Collapse (JOI18_collapse)	C++17	100 / 100	4485 ms	25904 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int B = 2020;
struct DSU{
    int path[100100], sz[100100], cnt;
    vector<pair<int, int>> mylog;
    void init(int n){for (int i=1;i<=n;i++){path[i] = i; sz[i] = 1;} mylog.clear(); cnt = 0;}
    int find(int s){
        if (s==path[s]) return s;
        return find(path[s]);
    }
    bool merge(int x, int y){
        //printf("merge: %d %d\n", x, y);
        x = find(x), y = find(y);
        if (x==y) return 0;
        cnt++;
        if (sz[x] > sz[y]) swap(x, y);

        path[x] = y;
        sz[y] += sz[x];
        mylog.emplace_back(x, sz[x]);
        return 1;
    }
    void rollback(int c){
        while(c--){
            auto [x, _sz] = mylog.back(); mylog.pop_back();
            sz[path[x]] -= _sz;
            path[x] = x;
            --cnt;
        }
    }
    int count(int x){return x - cnt;}
}dsu;

struct Edge{
    int x, y;
    Edge(){}
    Edge(int _x, int _y): x(_x), y(_y) {}
}E[200200];

struct Query{
    int w, p, i;
    Query(){}
    Query(int _w, int _p, int _i): w(_w), p(_p), i(_i) {}
};

vector<Query> bucket[110000];
map<int, int> mp[110000];
int idx[110000], updated[110000], on[110000], ans[110000];

bool cmpB(const Query &x, const Query &y){return x.p < y.p;}
bool cmpE(int x, int y){return E[x].y < E[y].y;}

void calc(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
    int c = T.size(), q = W.size();

    ///init
    for (int i=1;i<=c;i++){
        mp[i].clear();
        on[i] = 0;
        updated[i] = 0;
    }
    for (int i=0;i<=c/B;i++) bucket[i].clear();
    fill(E, E+c+1, Edge(0, 0));
    ///

    int Ecnt = 0;
    for (int i=1;i<=c;i++){
        int op, x, y;
        op = T[i-1], x = X[i-1], y = Y[i-1];

        if (x==y) {idx[i] = 0; continue;}
        if (x > y) swap(x, y);
        if (mp[x].find(y)==mp[x].end()){
            mp[x][y] = ++Ecnt;
            E[Ecnt] = Edge(x, y);
        }

        idx[i] = mp[x][y];
    }

    for (int i=1;i<=q;i++){
        int w, p;
        w = W[i-1], p = P[i-1];
        bucket[w/B].emplace_back(w, p, i);
    }

    vector<int> onE;

    for (int z=0;z<=c/B;z++){
        int l = z*B, r = (z+1)*B;
        for (int i=l;i<r;i++) if (idx[i]) updated[idx[i]] = 1;

        sort(bucket[z].begin(), bucket[z].end(), cmpB);
        dsu.init(n);
        int pt = 0;

        for (auto &[w, p, qi]:bucket[z]){
            while(pt < (int)onE.size() && E[onE[pt]].y <= p){
                if (!updated[onE[pt]]) dsu.merge(E[onE[pt]].x, E[onE[pt]].y);
                pt++;
            }

            for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1;

            int cnt = 0;
            for (int i=l;i<r;i++) if (idx[i] && on[idx[i]] && E[idx[i]].y <= p){
                if (dsu.merge(E[idx[i]].x, E[idx[i]].y)) cnt++;
            }

            //printf("ok %d -> %d\n", qi, dsu.count(p));
            ans[qi] += dsu.count(p);
            dsu.rollback(cnt);

            for (int i=l;i<=w;i++) if (idx[i]) on[idx[i]] ^= 1;
        }

        for (int i=l;i<r;i++) if (idx[i]) on[idx[i]] ^= 1, updated[idx[i]] = 0;

        vector<int> nE;
        for (auto &x:onE) if (on[x]) nE.push_back(x);
        for (int i=l;i<r;i++) if (on[idx[i]]) nE.push_back(idx[i]);

        sort(nE.begin(), nE.end(), cmpE);
        nE.erase(unique(nE.begin(), nE.end()), nE.end());
        swap(nE, onE);
    }
}

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
    for (auto &x:X) ++x;
    for (auto &x:Y) ++x;
    for (auto &x:W) ++x;
    for (auto &x:P) ++x;

    calc(N, T, X, Y, W, P);
    for (auto &x:X) x = N+1 - x;
    for (auto &y:Y) y = N+1 - y;
    for (auto &p:P) p = N - p;
    calc(N, T, X, Y, W, P);

    vector<int> ret(W.size());
    for (int i=0;i<(int)W.size();i++) ret[i] = ans[i+1];

	return ret;
}

Compilation message (stderr)

collapse.cpp: In function 'void calc(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:72:13: warning: variable 'op' set but not used [-Wunused-but-set-variable]
   72 |         int op, x, y;
      |             ^~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35