Submission #119086

#	Time	Username	Problem	Language	Result	Execution time	Memory
119086		evpipis	Collapse (JOI18_collapse)	C++14	0 / 100	15077 ms	15736 KiB

collapse

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 1e5+5;

struct segment_tree{
    int tree[4*len];

    segment_tree(){}

    void prop(int p, int l, int r){
        if (!tree[p] || l == r) return;

        tree[2*p] += tree[p];
        tree[2*p+1] += tree[p];
        tree[p] = 0;
    }

    void upd(int p, int l, int r, int i, int j, int x){
        prop(p, l, r);

        if (r < i || j < l)
            return;
        if (i <= l && r <= j)
            tree[p] += x;
        else{
            int mid = (l+r)/2;
            upd(2*p, l, mid, i, j, x);
            upd(2*p+1, mid+1, r, i, j, x);
        }
    }

    int ask(int p, int l, int r, int i){
        prop(p, l, r);

        if (l == r)
            return tree[p];

        int mid = (l+r)/2;
        if (i <= mid)
            return ask(2*p, l, mid, i);
        return ask(2*p+1, mid+1, r, i);
    }
};

segment_tree pref, suf;
int out[len], sz[len], par[len], n, m, q;
vector<ii> oper[4*len], st, todo[len];
map<ii, int> mym;

int fin(int i){
    if (par[i] == i) return i;
    return fin(i);
}

void print(segment_tree cur){
    for (int i = 0; i < n; i++)
        printf("%d ", cur.ask(1, 0, n-1, i));
    printf("\n");
}

void join(int i, int j){
    if (sz[i] > sz[j])
        par[j] = i, sz[i] += sz[j];
    else
        par[i] = j, sz[j] += sz[i];
}

void split(int i, int j){
    if (sz[i] > sz[j])
        par[j] = j, sz[i] -= sz[j];
    else
        par[i] = i, sz[j] -= sz[i];
}

void add(int p, int l, int r, int i, int j, ii v){
    if (r < i || j < l)
        return;
    if (i <= l && r <= j)
        oper[p].pb(v);
    else{
        int mid = (l+r)/2;
        add(2*p, l, mid, i, j, v);
        add(2*p+1, mid+1, r, i, j, v);
    }
}

void solve(int p, int l, int r){
    for (int i = 0; i < oper[p].size(); i++){
        int a = oper[p][i].fi, b = oper[p][i].se, x = fin(a), y = fin(b);
        if (x == y){
            oper[p][i].fi = -1;
        }
        else{
            pref.upd(1, 0, n-1, b, n-1, -1);
            suf.upd(1, 0, n-1, 0, a, -1);
            st.pb(mp(x, y));
            join(x, y);
        }
    }

    if (l == r){
        for (int i = 0; i < todo[l].size(); i++){
            int j = todo[l][i].fi, d = todo[l][i].se;
            out[d] = pref.ask(1, 0, n-1, j)+suf.ask(1, 0, n-1, j+1);
        }

        //printf("time = %d\n", l);
        //printf("pref = "), print(pref);
        //printf("suf = "), print(suf);
    }
    else{
        int mid = (l+r)/2;
        solve(2*p, l, mid);
        solve(2*p+1, mid+1, r);
    }

    for (int i = (int)oper[p].size()-1; i >= 0; i--){
        if (oper[p][i].fi == -1)
            continue;

        int a = oper[p][i].fi, b = oper[p][i].se;
        pref.upd(1, 0, n-1, b, n-1, 1);
        suf.upd(1, 0, n-1, 0, a, 1);
        split(st.back().fi, st.back().se);
        st.pop_back();
    }
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
    n = N, m = T.size(), q = W.size();

    for (int i = 0; i < n; i++){
        par[i] = i;
        sz[i] = 1;
        pref.upd(1, 0, n-1, i, i, i+1);
        suf.upd(1, 0, n-1, i, i, n-i);
    }

    for (int i = 0; i < m; i++){
        int t = T[i], x = X[i], y = Y[i];
        if (x > y)
            swap(x, y);

        if (t == 0)
            mym[mp(x, y)] = i;
        else{
            add(1, 0, m-1, mym[mp(x, y)], i-1, mp(x, y));
            mym.erase(mp(x, y));
        }
    }

    for (auto &it: mym)
        add(1, 0, m-1, it.se, m-1, it.fi);

    for (int i = 0; i < q; i++){
        int d = W[i], p = P[i];
        todo[d].pb(mp(p, i));
    }

    solve(1, 0, m-1);

    vector<int> out2(q, 0);
    for (int i = 0; i < q; i++)
        out2[i] = out[i];
	return out2;
}
/*
4 2 2
0 0 1
0 2 3
0 0
1 2
*/

Compilation message (stderr)

collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < oper[p].size(); i++){
                     ~~^~~~~~~~~~~~~~~~
collapse.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < todo[l].size(); i++){
                         ~~^~~~~~~~~~~~~~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:170:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < q; i++)
     ^~~
collapse.cpp:172:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return out2;
  ^~~~~~

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