oj.uz

답안 #119100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119100 2019-06-20T10:36:30 Z evpipis Collapse (JOI18_collapse) C++14
0 / 100
 15000 ms 15340 KB 
#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();
    }

    oper[p].clear();
}

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++){
        todo[i].clear();
    }
    mym.clear();

    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

100 8 6
0 3 99
0 2 1
0 5 98
1 99 3
0 40 80
0 30 80
1 80 30
1 1 2
7 8
7 98
0 38
4 50
2 12
6 90
*/

Compilation message

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:176:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < q; i++)
     ^~~
collapse.cpp:178:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return out2;
  ^~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Execution timed out 15010 ms 12288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 15340 KB Output is correct
2 Execution timed out 15073 ms 15224 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 15212 KB Output is correct
2 Execution timed out 15089 ms 15096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Execution timed out 15010 ms 12288 KB Time limit exceeded
3 Halted 0 ms 0 KB -