oj.uz

Submission #67534

# Submission time Handle Problem Language Result Execution time Memory
67534 2018-08-14T18:22:57 Z imeimi2000 Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 163656 KB 
#include "collapse.h"
#include <algorithm>
#include <functional>
#include <stdlib.h>
#include <time.h>
#include <map>

using namespace std;
typedef pair<int, int> pii;

int n, c, q;

vector<pii> seg[1 << 18];
vector<pii> query[100001];
vector<int> ans;
void insertLine(int i, int s, int e, int x, int y, pii v) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        seg[i].push_back(v);
        return;
    }
    int m = (s + e) / 2;
    insertLine(i << 1, s, m, x, y, v);
    insertLine(i << 1 | 1, m + 1, e, x, y, v);
}

pii par1[100001];
int fen1[100001];
int sz1[100001];
pii par2[100001];
int fen2[100001];
int sz2[100001];

struct operate {
    int * p;
    int t;
    int v;
};
void update(int fen[], int i, int v) {
    while (i <= n) {
        fen[i] += v;
        i += i & -i;
    }
}

int sum(int fen[], int i) {
    int ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

vector<operate> res;
void restore() {
    operate i = res.back();
    res.pop_back();
    if (i.t != 0) {
        update(i.p, i.v, i.t);
    }
    else {
        *i.p = i.v;
    }
}

int findDep(pii par[], int x) {
    if (par[x].first) return findDep(par, par[x].first) + 1;
    return 0;
}

int find(pii par[], int x, int t) {
    if (par[x].second <= t) return find(par, par[x].first, t);
    return x;
}

void saveSz(pii par[], int sz[], int x) {
    while (x) {
        res.push_back({ &sz[x], 0, sz[x] });
        x = par[x].first;
    }
}

void addSz(pii par[], int sz[], int x, int v) {
    while (x) {
        sz[x] += v;
        x = par[x].first;
    }
}

void merge(pii par[], int fen[], int sz[], int x, int y, int t) {
    int px = find(par, x, t);
    int py = find(par, y, t);
    if (px == py) return;
    if (sz[px] > sz[py]) swap(px, py);
    pii nxt = par[px];
    
    res.push_back({ &par[px].first, 0, nxt.first });
    res.push_back({ &par[px].second, 0, nxt.second });
    
    res.push_back({ fen, 1, nxt.second });
    res.push_back({ fen, -1, t });
    
    addSz(par, sz, nxt.first, sz[px]);
    par[px] = pii(py, t);
    addSz(par, sz, py, sz[px]);
    update(fen, nxt.second, -1);
    update(fen, t, 1);
    
    if (nxt.first) merge(par, fen, sz, nxt.first, py, nxt.second);
}

int answerQuery(int x) {
    return sum(fen1, x) + sum(fen2, n - x);
}

void dnc(int i, int s, int e) {
    int ps = res.size();
    for (pii p : seg[i]) {
        int x, y;
        tie(x, y) = p;
        ++x; ++y;
        saveSz(par1, sz1, x);
        saveSz(par1, sz1, y);
        saveSz(par2, sz2, x);
        saveSz(par2, sz2, y);
        merge(par1, fen1, sz1, x, y, y);
        merge(par2, fen2, sz2, x, y, n - x + 1);
    }
    if (s == e) {
        for (pii p : query[s]) {
            ans[p.second] = n - answerQuery(p.first);
        }
    }
    else {
        int m = (s + e) / 2;
        dnc(i << 1, s, m);
        dnc(i << 1 | 1, m + 1, e);
    }
    while (ps < res.size()) restore();
}

const int inf = 1e6;
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X,
	vector<int> Y, vector<int> W, vector<int> P) {
    for (int i = 1; i <= 100000; ++i) {
        par1[i] = par2[i] = pii(0, inf);
        sz1[i] = sz2[i] = 1;
    }
    n = N;
    c = T.size();
    q = W.size();
    ans.resize(q);
    
    {
        map<pii, int> mp;
        for (int i = 0; i < c; ++i) {
            if (X[i] > Y[i]) swap(X[i], Y[i]);
            if (T[i]) {
                auto it = mp.find(pii(X[i], Y[i]));
                insertLine(1, 1, c, it->second, i, pii(X[i], Y[i]));
                mp.erase(it);
            }
            else {
                mp[pii(X[i], Y[i])] = i + 1;
            }
        }
        for (auto i : mp) {
            insertLine(1, 1, c, i.second, c, i.first);
        }
    }
    for (int i = 0; i < q; ++i) {
        query[W[i] + 1].emplace_back(P[i] + 1, i);
    }
    dnc(1, 1, c);
    return ans;
}

Compilation message

collapse.cpp: In function 'void dnc(int, int, int)':
collapse.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ps < res.size()) restore();
            ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11640 KB Output is correct
2 Correct 13 ms 11640 KB Output is correct
3 Correct 13 ms 11640 KB Output is correct
4 Correct 13 ms 11640 KB Output is correct
5 Correct 20 ms 12048 KB Output is correct
6 Correct 34 ms 14692 KB Output is correct
7 Correct 16 ms 14692 KB Output is correct
8 Correct 12 ms 14692 KB Output is correct
9 Correct 19 ms 14692 KB Output is correct
10 Correct 25 ms 14692 KB Output is correct
11 Correct 35 ms 14692 KB Output is correct
12 Correct 31 ms 14692 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14692 KB Output is correct
2 Correct 37 ms 15036 KB Output is correct
3 Correct 242 ms 24132 KB Output is correct
4 Correct 66 ms 24132 KB Output is correct
5 Correct 358 ms 25660 KB Output is correct
6 Correct 100 ms 25660 KB Output is correct
7 Correct 1447 ms 163656 KB Output is correct
8 Correct 281 ms 163656 KB Output is correct
9 Correct 43 ms 163656 KB Output is correct
10 Correct 71 ms 163656 KB Output is correct
11 Correct 95 ms 163656 KB Output is correct
12 Correct 374 ms 163656 KB Output is correct
13 Correct 678 ms 163656 KB Output is correct
14 Execution timed out 15056 ms 163656 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 163656 KB Output is correct
2 Correct 38 ms 163656 KB Output is correct
3 Correct 39 ms 163656 KB Output is correct
4 Correct 49 ms 163656 KB Output is correct
5 Correct 48 ms 163656 KB Output is correct
6 Correct 88 ms 163656 KB Output is correct
7 Correct 1241 ms 163656 KB Output is correct
8 Execution timed out 15097 ms 163656 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11640 KB Output is correct
2 Correct 13 ms 11640 KB Output is correct
3 Correct 13 ms 11640 KB Output is correct
4 Correct 13 ms 11640 KB Output is correct
5 Correct 20 ms 12048 KB Output is correct
6 Correct 34 ms 14692 KB Output is correct
7 Correct 16 ms 14692 KB Output is correct
8 Correct 12 ms 14692 KB Output is correct
9 Correct 19 ms 14692 KB Output is correct
10 Correct 25 ms 14692 KB Output is correct
11 Correct 35 ms 14692 KB Output is correct
12 Correct 31 ms 14692 KB Output is correct
13 Correct 37 ms 14692 KB Output is correct
14 Correct 37 ms 15036 KB Output is correct
15 Correct 242 ms 24132 KB Output is correct
16 Correct 66 ms 24132 KB Output is correct
17 Correct 358 ms 25660 KB Output is correct
18 Correct 100 ms 25660 KB Output is correct
19 Correct 1447 ms 163656 KB Output is correct
20 Correct 281 ms 163656 KB Output is correct
21 Correct 43 ms 163656 KB Output is correct
22 Correct 71 ms 163656 KB Output is correct
23 Correct 95 ms 163656 KB Output is correct
24 Correct 374 ms 163656 KB Output is correct
25 Correct 678 ms 163656 KB Output is correct
26 Execution timed out 15056 ms 163656 KB Time limit exceeded
27 Halted 0 ms 0 KB -