#544711 (C++17) No.1215 都市消滅ビーム

提出ソース

結果

問題	No.1215 都市消滅ビーム
ユーザー	yosupot
提出日時	2020-08-30 18:08:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	12,975 bytes
コンパイル時間	2,429 ms
コンパイル使用メモリ	155,816 KB
実行使用メモリ	40,208 KB
最終ジャッジ日時	2024-11-15 14:54:12
合計ジャッジ時間	16,164 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	1 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	WA	-
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	659 ms 25,932 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	259 ms 16,896 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	9 ms 6,816 KB
testcase_22	AC	402 ms 17,052 KB
testcase_23	AC	366 ms 19,708 KB
testcase_24	WA	-
testcase_25	AC	204 ms 12,816 KB
testcase_26	AC	396 ms 20,696 KB
testcase_27	WA	-
testcase_28	AC	275 ms 12,780 KB
testcase_29	AC	231 ms 12,380 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	36 ms 12,840 KB
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	1,122 ms 39,672 KB
testcase_37	AC	1,204 ms 39,948 KB
testcase_38	WA	-
testcase_39	AC	1,198 ms 39,568 KB
testcase_40	AC	2 ms 6,824 KB
testcase_41	AC	1 ms 6,824 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL




#include <algorithm>

#include <array>

#include <bitset>

#include <cassert>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;



#include <unistd.h>

struct Scanner {
    int fd = -1;
    char line[(1 << 15) + 1];
    size_t st = 0, ed = 0;
    void reread() {
        memmove(line, line + st, ed - st);
        ed -= st;
        st = 0;
        ed += ::read(fd, line + ed, (1 << 15) - ed);
        line[ed] = '\0';
    }
    bool succ() {
        while (true) {
            if (st == ed) {
                reread();
                if (st == ed) return false;
            }
            while (st != ed && isspace(line[st])) st++;
            if (st != ed) break;
        }
        if (ed - st <= 50) {
            bool sep = false;
            for (size_t i = st; i < ed; i++) {
                if (isspace(line[i])) {
                    sep = true;
                    break;
                }
            }
            if (!sep) reread();
        }
        return true;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        while (true) {
            size_t sz = 0;
            while (st + sz < ed && !isspace(line[st + sz])) sz++;
            ref.append(line + st, sz);
            st += sz;
            if (!sz || st != ed) break;
            reread();
        }
        return true;
    }
    template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
    bool read_single(T& ref) {
        if (!succ()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        ref = T(0);
        while (isdigit(line[st])) {
            ref = 10 * ref + (line[st++] & 0xf);
        }
        if (neg) ref = -ref;
        return true;
    }
    template <class T> bool read_single(V<T>& ref) {
        for (auto& d : ref) {
            if (!read_single(d)) return false;
        }
        return true;
    }
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
    int read_unsafe() { return 0; }
    template <class H, class... T> int read_unsafe(H& h, T&... t) {
        bool f = read_single(h);
        if (!f) return 0;
        return 1 + read_unsafe(t...);
    }
    Scanner(FILE* fp) : fd(fileno(fp)) {}
};

struct Printer {
  public:
    template <bool F = false> void write() {}
    template <bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(' ');
        write_single(h);
        write<true>(t...);
    }
    template <class... T> void writeln(const T&... t) {
        write(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fp(_fp) {}
    ~Printer() { flush(); }

  private:
    static constexpr size_t SIZE = 1 << 15;
    FILE* fp;
    char line[SIZE], small[50];
    size_t pos = 0;
    void flush() {
        fwrite(line, 1, pos, fp);
        pos = 0;
    }
    void write_single(const char& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }
    template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
    void write_single(T val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val; // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char(0x30 | (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }
    void write_single(__int128 val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val; // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char(0x30 | (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }

    void write_single(const string& s) {
        for (char c : s) write_single(c);
    }
    void write_single(const char* s) {
        size_t len = strlen(s);
        for (size_t i = 0; i < len; i++) write_single(s[i]);
    }
    template <class T> void write_single(const V<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
};


struct LCA {
    int lg;
    VV<int> anc;
    V<int> dps;
    /// lとrの頂点のLCAを求める
    int query(int l, int r) {
        if (dps[l] < dps[r]) swap(l, r);
        int dd = dps[l] - dps[r];
        for (int i = lg - 1; i >= 0; i--) {
            if (dd < (1 << i)) continue;
            dd -= 1 << i;
            l = anc[i][l];
        }
        if (l == r) return l;
        for (int i = lg - 1; i >= 0; i--) {
            if (anc[i][l] == anc[i][r]) continue;
            tie(l, r) = tie(anc[i][l], anc[i][r]);
        }
        return anc[0][l];
    }
    int up(int p, int dist) {
        for (int i = lg - 1; i >= 0; i--) {
            if (dist >= (1 << i)) {
                dist -= 1 << i;
                p = anc[i][p];
            }
        }
        return p;
    }
    int dist(int l, int r) {
        int z = query(l, r);
        return dps[l] + dps[r] - 2 * dps[z];
    }
};

template <class E> struct LCAExec : LCA {
    const VV<E>& g;

    /// 事前処理を行う rはroot頂点のid
    LCAExec(const VV<E>& _g, int r) : g(_g) {
        int N = int(g.size());
        lg = 1;
        while ((1 << lg) < N) lg++;
        anc = VV<int>(lg, V<int>(N, -1));
        dps = V<int>(N);
        dfs(r, -1, 0);
        for (int i = 1; i < lg; i++) {
            for (int j = 0; j < N; j++) {
                anc[i][j] =
                    (anc[i - 1][j] == -1) ? -1 : anc[i - 1][anc[i - 1][j]];
            }
        }
    }

    void dfs(int p, int b, int now) {
        anc[0][p] = b;
        dps[p] = now;
        for (E e : g[p]) {
            if (e.to == b) continue;
            dfs(e.to, p, now + 1);
        }
    }
};

template <class E> LCA get_lca(const VV<E>& g, int r) {
    return LCAExec<E>(g, r);
}
// wavelet matrix
struct Wavelet {
    // space: 32N bits
    struct BitVector {
        V<int> _rank = {0};
        BitVector(V<char> v = V<char>()) {
            _rank.reserve(v.size() + 1);
            for (int d : v) _rank.push_back(_rank.back() + d);
        }
        int rank(bool f, int k) { return f ? _rank[k] : (k - _rank[k]); }
        int rank(bool f, int l, int r) { return rank(f, r) - rank(f, l); }
    };
    // space: 1.5N bits
    /*struct BitVector {
        V<ull> v;
        V<int> _rank;
        BitVector(V<char> _v = V<char>()) {
            int n = int(_v.size());
            v = V<ull>((n + 63) / 64);
            _rank = V<int>(v.size() + 1);
            for (int i = 0; i < n; i++) {
                if (_v[i]) {
                    v[i / 64] |= 1ULL << (i % 64);
                    _rank[i / 64 + 1]++;
                }
            }
            for (int i = 0; i < int(v.size()); i++) {
                _rank[i+1] += _rank[i];
            }
        }
        int rank(int k) {
            int a = _rank[k / 64];
            if (k % 64) a += __builtin_popcountll(v[k / 64] << (64 - k % 64));
            return a;
        }
        int rank(bool f, int k) { return f ? rank(k) : k - rank(k); }
        int rank(bool f, int l, int r) { return rank(f, r) - rank(f, l); }
    };*/

    int n, lg = 1;
    V<int> mid;
    V<BitVector> data;
    Wavelet(V<int> v = V<int>()) : n(int(v.size())) {
        int ma = 0;
        for (int x : v) ma = max(ma, x);
        while ((1 << lg) <= ma) lg++;
        mid = V<int>(lg);
        data = V<BitVector>(lg);
        for (int lv = lg - 1; lv >= 0; lv--) {
            V<char> buf;
            VV<int> nx(2);
            for (int d : v) {
                bool f = (d & (1 << lv)) > 0;
                buf.push_back(f);
                nx[f].push_back(d);
            }
            mid[lv] = int(nx[0].size());
            data[lv] = BitVector(buf);
            v.clear();
            v.insert(v.end(), nx[0].begin(), nx[0].end());
            v.insert(v.end(), nx[1].begin(), nx[1].end());
        }
    }
    pair<int, int> succ(bool f, int a, int b, int lv) {
        int na = data[lv].rank(f, a) + (f ? mid[lv] : 0);
        int nb = data[lv].rank(f, b) + (f ? mid[lv] : 0);
        return make_pair(na, nb);
    }
    // count i, s.t. (a <= i < b) && (v[i] < u)
    int rank(int a, int b, int u) {
        if ((1 << lg) <= u) return b - a;
        int ans = 0;
        for (int lv = lg - 1; lv >= 0; lv--) {
            bool f = (u & (1 << lv)) > 0;
            if (f) ans += data[lv].rank(false, a, b);
            tie(a, b) = succ(f, a, b, lv);
        }
        return ans;
    }
    // k-th(0-indexed!) number in v[a..b]
    int select(int a, int b, int k) {
        int u = 0;
        for (int lv = lg - 1; lv >= 0; lv--) {
            int le = data[lv].rank(false, a, b);
            bool f = (le <= k);
            if (f) {
                u += (1 << lv);
                k -= le;
            }
            tie(a, b) = succ(f, a, b, lv);
        }
        return u;
    }
};

struct CompressWavelet {
    Wavelet wt;
    V<ll> v, vidx;
    int zip(ll x) {
        return int(lower_bound(vidx.begin(), vidx.end(), x) - vidx.begin());
    }
    CompressWavelet(V<ll> _v = V<ll>()) : v(_v), vidx(v) {
        sort(vidx.begin(), vidx.end());
        vidx.erase(unique(vidx.begin(), vidx.end()), vidx.end());
        V<int> v2;
        for (auto d: v) v2.push_back(zip(d));
        wt = Wavelet(v2);
    }
    int rank(int a, int b, ll u) { return wt.rank(a, b, zip(u)); }
};

Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);

int main() {
    int n, k;
    sc.read(n, k);
    V<int> c(k);
    V<ll> d(k);
    for (int i = 0; i < k; i++) {
        sc.read(c[i]);
        c[i]--;
    }
    for (int i = 0; i < k; i++) {
        sc.read(d[i]);
    }

    struct E { int to; };
    VV<E> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        sc.read(u, v); u--; v--;
        g[u].push_back({v});
        g[v].push_back({u});
    }
    auto lca = get_lca(g, 0);


    int mid = lca.dps[lca.query(c[0], c[k - 1])];

    V<ll> spe;
    V<ll> ls(k), rs(k);
    V<int> lh(k), rh(k);
    {
        int pos = -1;
        for (int i = 0; i < k; i++) {
            pos = (pos == -1 ? c[i] : lca.query(pos, c[i]));
            ls[i] = d[i];
            if (i) ls[i] += ls[i - 1];

            lh[i] = lca.dps[pos];

            spe.push_back(ls[i] + lh[i]);
            lh[i] = min(lh[i], mid);
        }
    }
    {
        int pos = -1;
        for (int i = k - 1; i >= 0; i--) {
            pos = (pos == -1 ? c[i] : lca.query(pos, c[i]));

            rs[i] = d[i];
            if (i + 1 < k) rs[i] += rs[i + 1];

            rh[i] = lca.dps[pos];

            if (i) spe.push_back(rs[i] + rh[i]);
            rh[i] = min(rh[i], mid);
        }
    }

               ;
            ;

    CompressWavelet lwt(ls), rwt(rs);

    // x以下が何個あるか？
    auto solve = [&](ll x) {
        ll ans = 1; // -10^10^10
        for (ll y: spe) {
            if (y <= x) ans++;
        }
        {
            // lh <= rh
            int j = 0;
            for (int i = 0; i < k - 2; i++) {
                j = max(j, i + 1);
                while (i + 1 < j && lh[i] <= rh[j]) j--;
                // rs[j] + ls[i] + lh[i] <= x

                ans += rwt.rank(j + 1, k, x - ls[i] - lh[i] + 1);
            }
        }
        {
            // lh > rh
            int j = 0;
            for (int i = k - 1; i >= 2; i--) {
                j = min(j, i - 1);
                while (j < i - 1 && lh[j] > rh[i]) j++;
                ans += lwt.rank(0, j, x - rs[i] - rh[i] + 1);
            }
        }
        return ans;
    };

    ll alc = ll(k) * (k + 1) / 2 + 1;
    ll lw = -TEN(15), up = TEN(15);

            ;
    while (up - lw > 1) {
        ll md = (lw + up) / 2;
        if (solve(md) < (alc + 1) / 2) {
            lw = md;
        } else {
            up = md;
        }
    }
    pr.writeln(up);
    return 0;
}

yukicoder

結果

テストケース

ソースコード