Ideone.com

fork download

copy

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define inline inline __attribute__((always_inline))
 
using namespace std;
 
template <class Value, int MAX_SIZE>
class BufferedContainer {
    Value buf[MAX_SIZE];
    int sz = 0;
 
public:
    inline int size() const { return sz; }
    inline void clear() { sz = 0; }
    inline bool empty() const { return sz == 0; }
 
    inline void push(Value value) { buf[sz++] = value; }
    inline Value pop() { return buf[--sz]; }
 
    inline Value operator[](int i) { return buf[i]; }
 
    inline Value *begin() { return buf; }
    inline Value *end() { return buf + sz; }
};
 
constexpr int V = 5e4;
constexpr int E = 1e5;
constexpr int Q = 1e5;
constexpr int B = 1000;
 
struct Edge {
    int u, v, w;
};
 
struct Query {
    int v, w, t;
};
 
struct Update {
    int e, w, t;
};
 
int temp[E];
Edge edges[E];
int edge_order[E];
Query queries[B];
Update updates[B];
BufferedContainer<int, B> additional[B];
bool changed[E];
BufferedContainer<int, B> changed_edges;
BufferedContainer<int, V> searching;
int visited[V];
int answer[B];
 
namespace DSU
{
    int parent[V];
 
    void init(int n) {
        fill(parent, parent + n, -1);
    }
 
    int find_set(int u) {
        if (parent[u] < 0) return u;
        return parent[u] = find_set(parent[u]);
    }
 
    void union_sets(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return;
 
        if (parent[u] > parent[v]) swap(u, v);
        parent[u] += parent[v];
        parent[v] = u;
    }
}
 
vector<pair<int, int>> graph[V];
 
namespace subtaskLinear {
    int n;
    int tree[4 * V];
 
    void build(int id, int l, int r) {
        if (l == r) {
            tree[id] = edges[l - 1].w;
            return;
        }
        int m = l + r >> 1;
        build(id * 2, l, m);
        build(id * 2 + 1, m + 1, r);
        tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
    }
 
    void update(int id, int l, int r, int i, int w) {
        if (l == r) {
            tree[id] = w;
            return;
        }
        int m = l + r >> 1;
        if (i <= m)
            update(id * 2, l, m, i, w);
        else
            update(id * 2 + 1, m + 1, r, i, w);
        tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
    }
 
    int walk_left(int id, int l, int r, int i, int w) {
        if (l >= i) return 0;
        if (r < i) {
            if (tree[id] >= w) return 0;
            if (l == r) return l;
        }
        int m = l + r >> 1;
        int res = walk_left(id * 2 + 1, m + 1, r, i, w);
        return res ? res : walk_left(id * 2, l, m, i, w);
    }
 
    int walk_right(int id, int l, int r, int i, int w) {
        if (r < i) return n;
        if (l >= i) {
            if (tree[id] >= w) return n;
            if (l == r) return l;
        }
        int m = l + r >> 1;
        int res = walk_right(id * 2, l, m, i, w);
        return res != n ? res : walk_right(id * 2 + 1, m + 1, r, i, w);
    }
 
    void solve(int n) {
        if (n == 1) {
            int q;
            cin >> q;
 
            while (q--) {
                cout << '1' << '\n';
            }
            return;
        }
 
        subtaskLinear::n = n;
        build(1, 1, n - 1);
 
        int q;
        cin >> q;
 
        while (q--) {
            char type;
            cin >> type;
 
            int i, w;
            cin >> i >> w;
 
            if (type == '1') {
                update(1, 1, n - 1, i, w);
                continue;
            }
 
            cout << walk_right(1, 1, n - 1, i, w) - walk_left(1, 1, n - 1, i, w) << '\n';
        }
    }
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    // freopen("input.txt", "r", stdin);
 
    int nV, nE;
    cin >> nV >> nE;
 
    bool is_linear = nE == nV - 1;
 
    for (int e = 0; e < nE; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
 
        is_linear &= u == e && v == e + 1;
        edges[e] = {u, v, w};
    }
 
    if (is_linear) {
        subtaskLinear::solve(nV);
        return 0;
    }
 
    iota(edge_order, edge_order + nE, 0);
    sort(edge_order, edge_order + nE, [](int i, int j) {
        return edges[i].w > edges[j].w;
    });
 
    int nQU;
    cin >> nQU;
    int timer = 0;
 
    for (int block_start = 0; block_start < nQU; block_start += B) {
        const int block_size = min(B, nQU - block_start);
 
        int nQ = 0, nU = 0;
        changed_edges.clear();
 
        for (int t = 0; t < block_size; t++) {
            char type;
            cin >> type;
 
            int i, w;
            cin >> i >> w;
            i--;
 
            if (type == '1') {
                updates[nU++] = {i, w, nQ};
                if (!changed[i]) {
                    changed[i] = true;
                    changed_edges.push(i);
                }
            } else {
                queries[nQ] = {i, w, nQ};
                nQ++;
            }
        }
 
        int u = 0;
        for (int q = 0; q < nQ; q++) {
            while (u < nU && updates[u].t <= queries[q].t) {
                edges[updates[u].e].w = updates[u].w;
                u++;
            }
            additional[q].clear();
            for (int e : changed_edges) {
                if (edges[e].w >= queries[q].w) {
                    additional[q].push(e);
                }
            }
        }
        while (u < nU) {
            edges[updates[u].e].w = updates[u].w;
            u++;
        }
 
        sort(queries, queries + nQ, [](const Query &p, const Query &q) {
            return p.w > q.w;
        });
 
        DSU::init(nV);
        int i = 0;
 
        for (int q = 0; q < nQ; q++) {
            int w = queries[q].w;
 
            while (i < nE) {
                int e = edge_order[i];
                if (changed[e]) { i++; continue; }
                if (edges[e].w < w) break;
                DSU::union_sets(edges[e].u, edges[e].v);
                i++;
            }
 
            timer++;
 
            for (int e : additional[queries[q].t]) {
                int u = DSU::find_set(edges[e].u);
                int v = DSU::find_set(edges[e].v);
                if (u == v) continue;
                graph[u].emplace_back(v, timer);
                graph[v].emplace_back(u, timer);
            }
 
            searching.clear();
            int v = DSU::find_set(queries[q].v);
            searching.push(v);
            visited[v] = timer;
            int res = 0;
 
            while (!searching.empty()) {
                int u = searching.pop();
                res -= DSU::parent[u];
 
                for (auto [v, t] : graph[u]) {
                    if (t != timer) continue;
                    if (visited[v] == timer) continue;
                    visited[v] = timer;
                    searching.push(v);
                }
                graph[u].clear();
            }
 
            answer[queries[q].t] = res;
        }
 
        for (int q = 0; q < nQ; q++) {
            cout << answer[q] << '\n';
        }
 
        sort(changed_edges.begin(), changed_edges.end(), [](int e, int f) {
            return edges[e].w > edges[f].w;
        });
 
        i = 0;
        while (i < nE && changed[edge_order[i]]) i++;
 
        for (int j = 0, k = 0; k < nE; k++) {
            if (j == changed_edges.size() || i < nE && edges[edge_order[i]].w >= edges[changed_edges[j]].w) {
                temp[k] = edge_order[i++];
                while (i < nE && changed[edge_order[i]]) i++;
            } else {
                temp[k] = changed_edges[j++];
            }
        }
        copy(temp, temp + nE, edge_order);
 
        for (int e : changed_edges) {
            changed[e] = false;
        }
    }
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8bnVtZXJpYz4KI2RlZmluZSBpbmxpbmUgaW5saW5lIF9fYXR0cmlidXRlX18oKGFsd2F5c19pbmxpbmUpKQoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnRlbXBsYXRlIDxjbGFzcyBWYWx1ZSwgaW50IE1BWF9TSVpFPgpjbGFzcyBCdWZmZXJlZENvbnRhaW5lciB7CiAgICBWYWx1ZSBidWZbTUFYX1NJWkVdOwogICAgaW50IHN6ID0gMDsKCnB1YmxpYzoKICAgIGlubGluZSBpbnQgc2l6ZSgpIGNvbnN0IHsgcmV0dXJuIHN6OyB9CiAgICBpbmxpbmUgdm9pZCBjbGVhcigpIHsgc3ogPSAwOyB9CiAgICBpbmxpbmUgYm9vbCBlbXB0eSgpIGNvbnN0IHsgcmV0dXJuIHN6ID09IDA7IH0KCiAgICBpbmxpbmUgdm9pZCBwdXNoKFZhbHVlIHZhbHVlKSB7IGJ1ZltzeisrXSA9IHZhbHVlOyB9CiAgICBpbmxpbmUgVmFsdWUgcG9wKCkgeyByZXR1cm4gYnVmWy0tc3pdOyB9CgogICAgaW5saW5lIFZhbHVlIG9wZXJhdG9yW10oaW50IGkpIHsgcmV0dXJuIGJ1ZltpXTsgfQoKICAgIGlubGluZSBWYWx1ZSAqYmVnaW4oKSB7IHJldHVybiBidWY7IH0KICAgIGlubGluZSBWYWx1ZSAqZW5kKCkgeyByZXR1cm4gYnVmICsgc3o7IH0KfTsKCmNvbnN0ZXhwciBpbnQgViA9IDVlNDsKY29uc3RleHByIGludCBFID0gMWU1Owpjb25zdGV4cHIgaW50IFEgPSAxZTU7CmNvbnN0ZXhwciBpbnQgQiA9IDEwMDA7CgpzdHJ1Y3QgRWRnZSB7CiAgICBpbnQgdSwgdiwgdzsKfTsKCnN0cnVjdCBRdWVyeSB7CiAgICBpbnQgdiwgdywgdDsKfTsKCnN0cnVjdCBVcGRhdGUgewogICAgaW50IGUsIHcsIHQ7Cn07CgppbnQgdGVtcFtFXTsKRWRnZSBlZGdlc1tFXTsKaW50IGVkZ2Vfb3JkZXJbRV07ClF1ZXJ5IHF1ZXJpZXNbQl07ClVwZGF0ZSB1cGRhdGVzW0JdOwpCdWZmZXJlZENvbnRhaW5lcjxpbnQsIEI+IGFkZGl0aW9uYWxbQl07CmJvb2wgY2hhbmdlZFtFXTsKQnVmZmVyZWRDb250YWluZXI8aW50LCBCPiBjaGFuZ2VkX2VkZ2VzOwpCdWZmZXJlZENvbnRhaW5lcjxpbnQsIFY+IHNlYXJjaGluZzsKaW50IHZpc2l0ZWRbVl07CmludCBhbnN3ZXJbQl07CgpuYW1lc3BhY2UgRFNVCnsKICAgIGludCBwYXJlbnRbVl07CgogICAgdm9pZCBpbml0KGludCBuKSB7CiAgICAgICAgZmlsbChwYXJlbnQsIHBhcmVudCArIG4sIC0xKTsKICAgIH0KCiAgICBpbnQgZmluZF9zZXQoaW50IHUpIHsKICAgICAgICBpZiAocGFyZW50W3VdIDwgMCkgcmV0dXJuIHU7CiAgICAgICAgcmV0dXJuIHBhcmVudFt1XSA9IGZpbmRfc2V0KHBhcmVudFt1XSk7CiAgICB9CgogICAgdm9pZCB1bmlvbl9zZXRzKGludCB1LCBpbnQgdikgewogICAgICAgIHUgPSBmaW5kX3NldCh1KTsKICAgICAgICB2ID0gZmluZF9zZXQodik7CiAgICAgICAgaWYgKHUgPT0gdikgcmV0dXJuOwoKICAgICAgICBpZiAocGFyZW50W3VdID4gcGFyZW50W3ZdKSBzd2FwKHUsIHYpOwogICAgICAgIHBhcmVudFt1XSArPSBwYXJlbnRbdl07CiAgICAgICAgcGFyZW50W3ZdID0gdTsKICAgIH0KfQoKdmVjdG9yPHBhaXI8aW50LCBpbnQ+PiBncmFwaFtWXTsKCm5hbWVzcGFjZSBzdWJ0YXNrTGluZWFyIHsKICAgIGludCBuOwogICAgaW50IHRyZWVbNCAqIFZdOwoKICAgIHZvaWQgYnVpbGQoaW50IGlkLCBpbnQgbCwgaW50IHIpIHsKICAgICAgICBpZiAobCA9PSByKSB7CiAgICAgICAgICAgIHRyZWVbaWRdID0gZWRnZXNbbCAtIDFdLnc7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IG0gPSBsICsgciA+PiAxOwogICAgICAgIGJ1aWxkKGlkICogMiwgbCwgbSk7CiAgICAgICAgYnVpbGQoaWQgKiAyICsgMSwgbSArIDEsIHIpOwogICAgICAgIHRyZWVbaWRdID0gbWluKHRyZWVbaWQgKiAyXSwgdHJlZVtpZCAqIDIgKyAxXSk7CiAgICB9CgogICAgdm9pZCB1cGRhdGUoaW50IGlkLCBpbnQgbCwgaW50IHIsIGludCBpLCBpbnQgdykgewogICAgICAgIGlmIChsID09IHIpIHsKICAgICAgICAgICAgdHJlZVtpZF0gPSB3OwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBtID0gbCArIHIgPj4gMTsKICAgICAgICBpZiAoaSA8PSBtKQogICAgICAgICAgICB1cGRhdGUoaWQgKiAyLCBsLCBtLCBpLCB3KTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHVwZGF0ZShpZCAqIDIgKyAxLCBtICsgMSwgciwgaSwgdyk7CiAgICAgICAgdHJlZVtpZF0gPSBtaW4odHJlZVtpZCAqIDJdLCB0cmVlW2lkICogMiArIDFdKTsKICAgIH0KCiAgICBpbnQgd2Fsa19sZWZ0KGludCBpZCwgaW50IGwsIGludCByLCBpbnQgaSwgaW50IHcpIHsKICAgICAgICBpZiAobCA+PSBpKSByZXR1cm4gMDsKICAgICAgICBpZiAociA8IGkpIHsKICAgICAgICAgICAgaWYgKHRyZWVbaWRdID49IHcpIHJldHVybiAwOwogICAgICAgICAgICBpZiAobCA9PSByKSByZXR1cm4gbDsKICAgICAgICB9CiAgICAgICAgaW50IG0gPSBsICsgciA+PiAxOwogICAgICAgIGludCByZXMgPSB3YWxrX2xlZnQoaWQgKiAyICsgMSwgbSArIDEsIHIsIGksIHcpOwogICAgICAgIHJldHVybiByZXMgPyByZXMgOiB3YWxrX2xlZnQoaWQgKiAyLCBsLCBtLCBpLCB3KTsKICAgIH0KCiAgICBpbnQgd2Fsa19yaWdodChpbnQgaWQsIGludCBsLCBpbnQgciwgaW50IGksIGludCB3KSB7CiAgICAgICAgaWYgKHIgPCBpKSByZXR1cm4gbjsKICAgICAgICBpZiAobCA+PSBpKSB7CiAgICAgICAgICAgIGlmICh0cmVlW2lkXSA+PSB3KSByZXR1cm4gbjsKICAgICAgICAgICAgaWYgKGwgPT0gcikgcmV0dXJuIGw7CiAgICAgICAgfQogICAgICAgIGludCBtID0gbCArIHIgPj4gMTsKICAgICAgICBpbnQgcmVzID0gd2Fsa19yaWdodChpZCAqIDIsIGwsIG0sIGksIHcpOwogICAgICAgIHJldHVybiByZXMgIT0gbiA/IHJlcyA6IHdhbGtfcmlnaHQoaWQgKiAyICsgMSwgbSArIDEsIHIsIGksIHcpOwogICAgfQoKICAgIHZvaWQgc29sdmUoaW50IG4pIHsKICAgICAgICBpZiAobiA9PSAxKSB7CiAgICAgICAgICAgIGludCBxOwogICAgICAgICAgICBjaW4gPj4gcTsKCiAgICAgICAgICAgIHdoaWxlIChxLS0pIHsKICAgICAgICAgICAgICAgIGNvdXQgPDwgJzEnIDw8ICdcbic7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgc3VidGFza0xpbmVhcjo6biA9IG47CiAgICAgICAgYnVpbGQoMSwgMSwgbiAtIDEpOwoKICAgICAgICBpbnQgcTsKICAgICAgICBjaW4gPj4gcTsKCiAgICAgICAgd2hpbGUgKHEtLSkgewogICAgICAgICAgICBjaGFyIHR5cGU7CiAgICAgICAgICAgIGNpbiA+PiB0eXBlOwoKICAgICAgICAgICAgaW50IGksIHc7CiAgICAgICAgICAgIGNpbiA+PiBpID4+IHc7CgogICAgICAgICAgICBpZiAodHlwZSA9PSAnMScpIHsKICAgICAgICAgICAgICAgIHVwZGF0ZSgxLCAxLCBuIC0gMSwgaSwgdyk7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgY291dCA8PCB3YWxrX3JpZ2h0KDEsIDEsIG4gLSAxLCBpLCB3KSAtIHdhbGtfbGVmdCgxLCAxLCBuIC0gMSwgaSwgdykgPDwgJ1xuJzsKICAgICAgICB9CiAgICB9Cn0KCnNpZ25lZCBtYWluKCkKewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKICAgIGNvdXQudGllKE5VTEwpOwoKICAgIC8vIGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwoKICAgIGludCBuViwgbkU7CiAgICBjaW4gPj4gblYgPj4gbkU7CgogICAgYm9vbCBpc19saW5lYXIgPSBuRSA9PSBuViAtIDE7CgogICAgZm9yIChpbnQgZSA9IDA7IGUgPCBuRTsgZSsrKSB7CiAgICAgICAgaW50IHUsIHYsIHc7CiAgICAgICAgY2luID4+IHUgPj4gdiA+PiB3OwogICAgICAgIHUtLSwgdi0tOwoKICAgICAgICBpc19saW5lYXIgJj0gdSA9PSBlICYmIHYgPT0gZSArIDE7CiAgICAgICAgZWRnZXNbZV0gPSB7dSwgdiwgd307CiAgICB9CgogICAgaWYgKGlzX2xpbmVhcikgewogICAgICAgIHN1YnRhc2tMaW5lYXI6OnNvbHZlKG5WKTsKICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICBpb3RhKGVkZ2Vfb3JkZXIsIGVkZ2Vfb3JkZXIgKyBuRSwgMCk7CiAgICBzb3J0KGVkZ2Vfb3JkZXIsIGVkZ2Vfb3JkZXIgKyBuRSwgW10oaW50IGksIGludCBqKSB7CiAgICAgICAgcmV0dXJuIGVkZ2VzW2ldLncgPiBlZGdlc1tqXS53OwogICAgfSk7CgogICAgaW50IG5RVTsKICAgIGNpbiA+PiBuUVU7CiAgICBpbnQgdGltZXIgPSAwOwoKICAgIGZvciAoaW50IGJsb2NrX3N0YXJ0ID0gMDsgYmxvY2tfc3RhcnQgPCBuUVU7IGJsb2NrX3N0YXJ0ICs9IEIpIHsKICAgICAgICBjb25zdCBpbnQgYmxvY2tfc2l6ZSA9IG1pbihCLCBuUVUgLSBibG9ja19zdGFydCk7CgogICAgICAgIGludCBuUSA9IDAsIG5VID0gMDsKICAgICAgICBjaGFuZ2VkX2VkZ2VzLmNsZWFyKCk7CgogICAgICAgIGZvciAoaW50IHQgPSAwOyB0IDwgYmxvY2tfc2l6ZTsgdCsrKSB7CiAgICAgICAgICAgIGNoYXIgdHlwZTsKICAgICAgICAgICAgY2luID4+IHR5cGU7CgogICAgICAgICAgICBpbnQgaSwgdzsKICAgICAgICAgICAgY2luID4+IGkgPj4gdzsKICAgICAgICAgICAgaS0tOwoKICAgICAgICAgICAgaWYgKHR5cGUgPT0gJzEnKSB7CiAgICAgICAgICAgICAgICB1cGRhdGVzW25VKytdID0ge2ksIHcsIG5RfTsKICAgICAgICAgICAgICAgIGlmICghY2hhbmdlZFtpXSkgewogICAgICAgICAgICAgICAgICAgIGNoYW5nZWRbaV0gPSB0cnVlOwogICAgICAgICAgICAgICAgICAgIGNoYW5nZWRfZWRnZXMucHVzaChpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIHF1ZXJpZXNbblFdID0ge2ksIHcsIG5RfTsKICAgICAgICAgICAgICAgIG5RKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGludCB1ID0gMDsKICAgICAgICBmb3IgKGludCBxID0gMDsgcSA8IG5ROyBxKyspIHsKICAgICAgICAgICAgd2hpbGUgKHUgPCBuVSAmJiB1cGRhdGVzW3VdLnQgPD0gcXVlcmllc1txXS50KSB7CiAgICAgICAgICAgICAgICBlZGdlc1t1cGRhdGVzW3VdLmVdLncgPSB1cGRhdGVzW3VdLnc7CiAgICAgICAgICAgICAgICB1Kys7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgYWRkaXRpb25hbFtxXS5jbGVhcigpOwogICAgICAgICAgICBmb3IgKGludCBlIDogY2hhbmdlZF9lZGdlcykgewogICAgICAgICAgICAgICAgaWYgKGVkZ2VzW2VdLncgPj0gcXVlcmllc1txXS53KSB7CiAgICAgICAgICAgICAgICAgICAgYWRkaXRpb25hbFtxXS5wdXNoKGUpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHdoaWxlICh1IDwgblUpIHsKICAgICAgICAgICAgZWRnZXNbdXBkYXRlc1t1XS5lXS53ID0gdXBkYXRlc1t1XS53OwogICAgICAgICAgICB1Kys7CiAgICAgICAgfQoKICAgICAgICBzb3J0KHF1ZXJpZXMsIHF1ZXJpZXMgKyBuUSwgW10oY29uc3QgUXVlcnkgJnAsIGNvbnN0IFF1ZXJ5ICZxKSB7CiAgICAgICAgICAgIHJldHVybiBwLncgPiBxLnc7CiAgICAgICAgfSk7CgogICAgICAgIERTVTo6aW5pdChuVik7CiAgICAgICAgaW50IGkgPSAwOwoKICAgICAgICBmb3IgKGludCBxID0gMDsgcSA8IG5ROyBxKyspIHsKICAgICAgICAgICAgaW50IHcgPSBxdWVyaWVzW3FdLnc7CgogICAgICAgICAgICB3aGlsZSAoaSA8IG5FKSB7CiAgICAgICAgICAgICAgICBpbnQgZSA9IGVkZ2Vfb3JkZXJbaV07CiAgICAgICAgICAgICAgICBpZiAoY2hhbmdlZFtlXSkgeyBpKys7IGNvbnRpbnVlOyB9CiAgICAgICAgICAgICAgICBpZiAoZWRnZXNbZV0udyA8IHcpIGJyZWFrOwogICAgICAgICAgICAgICAgRFNVOjp1bmlvbl9zZXRzKGVkZ2VzW2VdLnUsIGVkZ2VzW2VdLnYpOwogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICB9CgogICAgICAgICAgICB0aW1lcisrOwoKICAgICAgICAgICAgZm9yIChpbnQgZSA6IGFkZGl0aW9uYWxbcXVlcmllc1txXS50XSkgewogICAgICAgICAgICAgICAgaW50IHUgPSBEU1U6OmZpbmRfc2V0KGVkZ2VzW2VdLnUpOwogICAgICAgICAgICAgICAgaW50IHYgPSBEU1U6OmZpbmRfc2V0KGVkZ2VzW2VdLnYpOwogICAgICAgICAgICAgICAgaWYgKHUgPT0gdikgY29udGludWU7CiAgICAgICAgICAgICAgICBncmFwaFt1XS5lbXBsYWNlX2JhY2sodiwgdGltZXIpOwogICAgICAgICAgICAgICAgZ3JhcGhbdl0uZW1wbGFjZV9iYWNrKHUsIHRpbWVyKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgc2VhcmNoaW5nLmNsZWFyKCk7CiAgICAgICAgICAgIGludCB2ID0gRFNVOjpmaW5kX3NldChxdWVyaWVzW3FdLnYpOwogICAgICAgICAgICBzZWFyY2hpbmcucHVzaCh2KTsKICAgICAgICAgICAgdmlzaXRlZFt2XSA9IHRpbWVyOwogICAgICAgICAgICBpbnQgcmVzID0gMDsKCiAgICAgICAgICAgIHdoaWxlICghc2VhcmNoaW5nLmVtcHR5KCkpIHsKICAgICAgICAgICAgICAgIGludCB1ID0gc2VhcmNoaW5nLnBvcCgpOwogICAgICAgICAgICAgICAgcmVzIC09IERTVTo6cGFyZW50W3VdOwoKICAgICAgICAgICAgICAgIGZvciAoYXV0byBbdiwgdF0gOiBncmFwaFt1XSkgewogICAgICAgICAgICAgICAgICAgIGlmICh0ICE9IHRpbWVyKSBjb250aW51ZTsKICAgICAgICAgICAgICAgICAgICBpZiAodmlzaXRlZFt2XSA9PSB0aW1lcikgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgdmlzaXRlZFt2XSA9IHRpbWVyOwogICAgICAgICAgICAgICAgICAgIHNlYXJjaGluZy5wdXNoKHYpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZ3JhcGhbdV0uY2xlYXIoKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgYW5zd2VyW3F1ZXJpZXNbcV0udF0gPSByZXM7CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBxID0gMDsgcSA8IG5ROyBxKyspIHsKICAgICAgICAgICAgY291dCA8PCBhbnN3ZXJbcV0gPDwgJ1xuJzsKICAgICAgICB9CgogICAgICAgIHNvcnQoY2hhbmdlZF9lZGdlcy5iZWdpbigpLCBjaGFuZ2VkX2VkZ2VzLmVuZCgpLCBbXShpbnQgZSwgaW50IGYpIHsKICAgICAgICAgICAgcmV0dXJuIGVkZ2VzW2VdLncgPiBlZGdlc1tmXS53OwogICAgICAgIH0pOwoKICAgICAgICBpID0gMDsKICAgICAgICB3aGlsZSAoaSA8IG5FICYmIGNoYW5nZWRbZWRnZV9vcmRlcltpXV0pIGkrKzsKCiAgICAgICAgZm9yIChpbnQgaiA9IDAsIGsgPSAwOyBrIDwgbkU7IGsrKykgewogICAgICAgICAgICBpZiAoaiA9PSBjaGFuZ2VkX2VkZ2VzLnNpemUoKSB8fCBpIDwgbkUgJiYgZWRnZXNbZWRnZV9vcmRlcltpXV0udyA+PSBlZGdlc1tjaGFuZ2VkX2VkZ2VzW2pdXS53KSB7CiAgICAgICAgICAgICAgICB0ZW1wW2tdID0gZWRnZV9vcmRlcltpKytdOwogICAgICAgICAgICAgICAgd2hpbGUgKGkgPCBuRSAmJiBjaGFuZ2VkW2VkZ2Vfb3JkZXJbaV1dKSBpKys7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICB0ZW1wW2tdID0gY2hhbmdlZF9lZGdlc1tqKytdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGNvcHkodGVtcCwgdGVtcCArIG5FLCBlZGdlX29yZGVyKTsKCiAgICAgICAgZm9yIChpbnQgZSA6IGNoYW5nZWRfZWRnZXMpIHsKICAgICAgICAgICAgY2hhbmdlZFtlXSA9IGZhbHNlOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gMDsKfQ==

Success #stdin #stdout 0.01s 11672KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/jU4vcQ

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language