oj.uz

답안 #679454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679454 2023-01-08T09:55:29 Z qwerasdfzxcl Collapse (JOI18_collapse) C++17
5 / 100
 5785 ms 49488 KB 
#include "collapse.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int B = 5050;
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[100100];

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

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

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

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 8012 KB Output is correct
2 Correct 40 ms 7676 KB Output is correct
3 Correct 42 ms 7688 KB Output is correct
4 Correct 43 ms 7700 KB Output is correct
5 Correct 375 ms 8016 KB Output is correct
6 Correct 303 ms 8148 KB Output is correct
7 Correct 39 ms 7756 KB Output is correct
8 Correct 40 ms 7732 KB Output is correct
9 Correct 182 ms 8208 KB Output is correct
10 Correct 307 ms 8232 KB Output is correct
11 Correct 346 ms 8316 KB Output is correct
12 Correct 342 ms 8316 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 729 ms 11828 KB Output is correct
2 Correct 703 ms 11728 KB Output is correct
3 Runtime error 4056 ms 36312 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 701 ms 11804 KB Output is correct
2 Correct 701 ms 11844 KB Output is correct
3 Correct 727 ms 11880 KB Output is correct
4 Correct 743 ms 11908 KB Output is correct
5 Correct 1152 ms 12140 KB Output is correct
6 Correct 5785 ms 12724 KB Output is correct
7 Correct 5080 ms 22308 KB Output is correct
8 Runtime error 2904 ms 49488 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 8012 KB Output is correct
2 Correct 40 ms 7676 KB Output is correct
3 Correct 42 ms 7688 KB Output is correct
4 Correct 43 ms 7700 KB Output is correct
5 Correct 375 ms 8016 KB Output is correct
6 Correct 303 ms 8148 KB Output is correct
7 Correct 39 ms 7756 KB Output is correct
8 Correct 40 ms 7732 KB Output is correct
9 Correct 182 ms 8208 KB Output is correct
10 Correct 307 ms 8232 KB Output is correct
11 Correct 346 ms 8316 KB Output is correct
12 Correct 342 ms 8316 KB Output is correct
13 Correct 729 ms 11828 KB Output is correct
14 Correct 703 ms 11728 KB Output is correct
15 Runtime error 4056 ms 36312 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -