oj.uz

Submission #119110

# Submission time Handle Problem Language Result Execution time Memory
119110 2019-06-20T11:11:57 Z evpipis Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 21424 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> adj[len];
int vis[len], nex[len];

void dfs(int u){
    vis[u] = 1;
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        if (!vis[v])
            dfs(v);
    }
}

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 < m; i++)
        if (X[i] > Y[i])
            swap(X[i], Y[i]);

    for (int i = 0; i < m; i++){
        if (T[i] == 1)
            continue;

        nex[i] = m-1;
        for (int j = i+1; j < m; j++)
            if (mp(X[i], Y[i]) == mp(X[j], Y[j])){
                nex[i] = j-1;
                break;
            }
    }

    vector<int> out3(q, 0);
    for (int i = 0; i < q; i++){
        int d = W[i], p = P[i];
        for (int j = 0; j < n; j++)
            adj[j].clear(), vis[j] = 0;

        for (int j = 0; j < m; j++){
            if (T[j] == 0 && j <= d && nex[j] >= d && (Y[j] <= p || X[j] >= p+1))
                adj[X[j]].pb(Y[j]), adj[Y[j]].pb(X[j]);
        }

        out3[i] = 0;
        for (int j = 0; j < n; j++)
            if (!vis[j])
                out3[i]++, dfs(j);
    }

    return out3;

    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 'void dfs(int)':
collapse.cpp:143:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
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:223:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < q; i++)
     ^~~
collapse.cpp:225:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return out2;
  ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14720 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 16 ms 14592 KB Output is correct
5 Correct 118 ms 14720 KB Output is correct
6 Correct 177 ms 14840 KB Output is correct
7 Correct 120 ms 14712 KB Output is correct
8 Correct 123 ms 14652 KB Output is correct
9 Correct 225 ms 14968 KB Output is correct
10 Correct 304 ms 14968 KB Output is correct
11 Correct 649 ms 15016 KB Output is correct
12 Correct 440 ms 14956 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16384 KB Output is correct
2 Correct 39 ms 16376 KB Output is correct
3 Execution timed out 15035 ms 20472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16504 KB Output is correct
2 Correct 41 ms 16376 KB Output is correct
3 Correct 49 ms 16892 KB Output is correct
4 Correct 61 ms 16888 KB Output is correct
5 Correct 492 ms 17140 KB Output is correct
6 Correct 3018 ms 17528 KB Output is correct
7 Execution timed out 15045 ms 21424 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14720 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 16 ms 14592 KB Output is correct
5 Correct 118 ms 14720 KB Output is correct
6 Correct 177 ms 14840 KB Output is correct
7 Correct 120 ms 14712 KB Output is correct
8 Correct 123 ms 14652 KB Output is correct
9 Correct 225 ms 14968 KB Output is correct
10 Correct 304 ms 14968 KB Output is correct
11 Correct 649 ms 15016 KB Output is correct
12 Correct 440 ms 14956 KB Output is correct
13 Correct 34 ms 16384 KB Output is correct
14 Correct 39 ms 16376 KB Output is correct
15 Execution timed out 15035 ms 20472 KB Time limit exceeded
16 Halted 0 ms 0 KB -