Submission #371356


Source Code Expand

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <cstdio>
#include <bitset>

using namespace std;
typedef long long ll;

const ll INF = 1LL<<55;
template<int N>
struct ETTree {
    struct Node;
    typedef Node* NP;
    static Node last_d;
    static NP last;
    struct Node {
        NP p, l, r;
        int sz, idl, idr;
        typedef pair<ll, int> P;
        P d, mi;
        Node(int idl, int idr, int idx, ll d) :p(nullptr), l(last), r(last), sz(1), idl(idl), idr(idr), 
         d(P(d, idx)), mi(P(d, idx)) {}
        Node() : l(nullptr), r(nullptr), sz(0) {}

        //pushをすると、pushをした頂点とその子の"すべて"の値の正当性が保証される
        void push() { 
            assert(sz);
        }
        NP update() {
            assert(this != last);
            sz = 1+l->sz+r->sz;
            mi = d;
            if (l->sz) {
                mi = min(mi, l->mi);
            }
            if (r->sz) {
                mi = min(mi, r->mi);
            }
            return this;
        }
        void setdata(int idx, ll dd) {
            d = P(dd, idx);
            update();
        }
        void adddata(ll dd) {
            d.first += dd;
            update();
        }
        inline int pos() {
            if (p) {
                if (p->l == this) return -1;
                if (p->r == this) return 1;
            }
            return 0;
        }
        void rot() {
            NP qq = p->p;
            int pps = p->pos();
            if (p->l == this) {
                p->l = r; r->p = p;
                r = p; p->p = this;
            } else {
                p->r = l; l->p = p;
                l = p; p->p = this;
            }
            p->update(); update();
            p = qq;
            if (!pps) return;
            if (pps == -1) {
                qq->l = this;
            } else {
                qq->r = this;
            }
            qq->update();
        }
        NP splay() {
            assert(this != last);
            supush();
            int ps;
            while ((ps = pos())) {
                int pps = p->pos();
                if (!pps) {
                    rot();
                } else if (ps == pps) {
                    p->rot(); rot();
                } else {
                    rot(); rot();
                }
            }
            return this;
        }
        void supush() {
            if (pos()) {
                p->supush();
            }
            push();
        }
        void debug() {
            if (this == last) return;
            push();
            l->debug();
            printf("(%d-%d-{%lld %d %lld %d}) ", idl, idr, d.first, d.second, mi.first, mi.second);
            r->debug();
        }
    };
    typedef pair<int, int> P;
    map<int, int> mp[N+1];
    Node pool[2*N];
    ETTree() {
        for (int i = 0; i < N; i++) {
            pool[2*i] = Node(N, i, -1, INF);
            pool[2*i+1] = Node(i, N, -1, INF);
            merge(pool+2*i, pool+2*i+1);
            mp[N][i] = 2*i;
            mp[i][N] = 2*i+1;
        }
    }
    void debug(int d) {
        tree(d)->debug();
    }

    NP tree(int d) {
        assert(0 <= d && d < N);
        return (&pool[mp[d].begin()->second])->splay();
    }
    NP merge(NP l, NP r) {
        if (l == last) return r;
        if (r == last) return l;
        r = at(r, 0);
        r->l = l;
        l->p = r;
        return r->update();
    }
    pair<NP, NP> split(NP n, int k) {
        if (!k) return {last, n};
        if (n->sz == k) return {n, last};
        n = at(n, k);
        NP m = n->l;
        m->p = nullptr;
        n->l = last;
        n->update();
        return {m, n};
    }
    NP at(NP n, int k) {
        assert(n != last);
        n->push();
        if (k < n->l->sz) {
            return at(n->l, k);
        } else if (k == n->l->sz) {
            n->splay();
            return n;
        } else {
            return at(n->r, k-(n->l->sz+1));
        }
    }

    //yの子としてxを追加
    void evert(int x) {
        int rt = root(x);
        NP xt = tree(x);
        auto sp = split(xt, xt->l->sz);
        NP L, ML, MR, R;
        tie(L, ML) = split(sp.first, 1);
        tie(MR, R) = split(sp.second, sp.second->sz-1);
        assert(L->idl == N && L->idr == rt && R->idl == rt && R->idr == N);
        int lp = mp[N][rt], rp = mp[rt][N];
        pool[lp].idr = x; pool[rp].idl = x;
        mp[N].erase(rt); mp[rt].erase(N);
        mp[N][x] = lp; mp[x][N] = rp;
        merge(merge(merge(L, MR), ML), R);
    }
    void link(int x, int y, int idx, ll d) {
        assert(mp[x].count(N));
//        printf("link %d %d\n", x, y);
        NP xt = tree(x);
        NP yt = tree(y);
        //ytの前にtree(x)を入れたい
        int lp = mp[N][x], rp = mp[x][N];
        pool[lp].splay();
        pool[lp].idl = y;
        pool[lp].setdata(idx, d);
        pool[rp].splay();
        pool[rp].idr = y;
        pool[rp].setdata(idx, d);
        mp[N].erase(x); mp[x].erase(N);
        mp[y][x] = lp; mp[x][y] = rp;
        xt->splay();
        yt->splay();
        auto sp = split(yt, yt->l->sz);
        merge(merge(sp.first, xt), sp.second);
    }
    void cut(int x, int y) {
        assert(mp[x].count(y));
        int lp = mp[y][x], rp = mp[x][y];
        pool[lp].splay();
        pool[lp].idl = N;
        pool[lp].setdata(-1, INF);
        pool[rp].splay();
        pool[rp].idr = N;
        pool[rp].setdata(-1, INF);
        NP lx = pool+lp, rx = pool+rp;
        mp[y].erase(x); mp[x].erase(y);
        mp[N][x] = lp; mp[x][N] = rp;
        // L M R
        NP L, M, R;
        rx->splay();
        R = split(rx, rx->l->sz+1).second;
        lx->splay();
        tie(L, M) = split(lx, lx->l->sz);
        merge(L, R);
    }
    int root(int x) {
        NP xt = tree(x);
        return at(xt, 0)->idr;
    }
    void set(int x, int y, ll d) {
        int lp = mp[x][y], rp = mp[y][x];
        pool[lp].splay();
        pool[lp].adddata(d);
        pool[rp].splay();
        pool[rp].idr = y;
        pool[rp].adddata(d);
    }
    pair<int, int> get(int x) {
        NP xt = tree(x);
        return xt->mi;
    }
    //debug用 めっちゃ重いよ
    void scan() {
        for (int i = 0; i <= N; i++) {
            for (auto p: mp[i]) {
                assert(pool[p.second].idl == i);
                assert(pool[p.second].idr == p.first);
            }
        }
    }
};
template<int N>
typename ETTree<N>::Node ETTree<N>::last_d = ETTree::Node();
template<int N>
typename ETTree<N>::NP ETTree<N>::last = &last_d;

const int MN = 100100;

ETTree<MN> et;

typedef pair<int, int> E;
E e[MN];
bool used[MN];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n-1; i++) {
//        printf("e %d\n", i);
        int a, b, c;
        cin >> a >> b >> c; a--; b--;
        e[i] = E(a, b);
//        et.debug(a); printf("ev %d\n", a);
        et.evert(a);
//        et.debug(a); printf("lif %d\n", a);
//        et.debug(b); printf("lif %d\n", b);
        et.link(a, b, i, c);
//        et.debug(a); printf("lie %d\n", a);
//        et.debug(b); printf("lie %d\n", b);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, d;
            cin >> x >> d; x--;
            et.set(e[x].first, e[x].second, d);
        } else {
            int x;
            cin >> x; x--;
            if (used[x]) {
                cout << -1 << endl;
                continue;
            }
//            printf("get %d\n", e[x].first );
            auto res = et.get(e[x].first).second;
            used[res] = true;
            et.cut(e[res].first, e[res].second);
            printf("%d\n", res+1);
        }
//        et.debug(0); printf("de\n");
    }
    return 0;
}

Submission Info

Submission Time
Task I - 盆栽
User yosupo
Language C++11 (GCC 4.9.2)
Score 300
Code Size 8184 Byte
Status AC
Exec Time 1606 ms
Memory 32932 KB

Judge Result

Set Name Subtask All
Score / Max Score 30 / 30 270 / 270
Status
AC × 17
AC × 50
Set Name Test Cases
Subtask atetubou-challenge1.in, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 146 ms 29664 KB
scrambled_01.txt AC 145 ms 29724 KB
scrambled_02.txt AC 141 ms 29720 KB
scrambled_03.txt AC 140 ms 29732 KB
scrambled_04.txt AC 141 ms 29720 KB
scrambled_05.txt AC 142 ms 29724 KB
scrambled_06.txt AC 139 ms 29728 KB
scrambled_07.txt AC 143 ms 29728 KB
scrambled_08.txt AC 143 ms 29724 KB
scrambled_09.txt AC 143 ms 29780 KB
scrambled_10.txt AC 139 ms 29728 KB
scrambled_11.txt AC 1424 ms 30620 KB
scrambled_12.txt AC 1430 ms 30624 KB
scrambled_13.txt AC 1492 ms 30628 KB
scrambled_14.txt AC 1484 ms 30648 KB
scrambled_15.txt AC 1440 ms 30624 KB
scrambled_16.txt AC 1430 ms 30624 KB
scrambled_17.txt AC 1475 ms 30628 KB
scrambled_18.txt AC 1461 ms 30624 KB
scrambled_19.txt AC 1455 ms 30640 KB
scrambled_20.txt AC 1471 ms 30632 KB
scrambled_21.txt AC 1269 ms 32932 KB
scrambled_22.txt AC 145 ms 29728 KB
scrambled_23.txt AC 143 ms 29728 KB
scrambled_24.txt AC 141 ms 29732 KB
scrambled_25.txt AC 145 ms 29724 KB
scrambled_26.txt AC 144 ms 29724 KB
scrambled_27.txt AC 1518 ms 29772 KB
scrambled_28.txt AC 1571 ms 29780 KB
scrambled_29.txt AC 1597 ms 29728 KB
scrambled_30.txt AC 1601 ms 29728 KB
scrambled_31.txt AC 1606 ms 29732 KB
scrambled_32.txt AC 138 ms 29728 KB
subtask_00.txt AC 138 ms 29724 KB
subtask_01.txt AC 149 ms 29736 KB
subtask_02.txt AC 146 ms 29732 KB
subtask_03.txt AC 147 ms 29724 KB
subtask_04.txt AC 148 ms 29724 KB
subtask_05.txt AC 148 ms 29728 KB
subtask_06.txt AC 149 ms 29760 KB
subtask_07.txt AC 146 ms 29732 KB
subtask_08.txt AC 149 ms 29736 KB
subtask_09.txt AC 145 ms 29740 KB
subtask_10.txt AC 146 ms 29728 KB
subtask_11.txt AC 149 ms 29728 KB
subtask_12.txt AC 149 ms 29732 KB
subtask_13.txt AC 152 ms 29732 KB
subtask_14.txt AC 150 ms 29728 KB
subtask_15.txt AC 145 ms 29716 KB
subtask_16.txt AC 134 ms 29720 KB