#1010065 (C++17) No.2892 Lime and Karin

提出ソース

結果

問題	No.2892 Lime and Karin
ユーザー	Rubikun
提出日時	2024-09-13 22:03:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	312 ms / 8,000 ms
コード長	14,561 bytes
コンパイル時間	2,233 ms
コンパイル使用メモリ	209,872 KB
実行使用メモリ	20,164 KB
最終ジャッジ日時	2024-09-13 22:04:14
合計ジャッジ時間	11,577 ms
ジャッジサーバーID （参考情報）	judge6 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 5,888 KB
testcase_01	AC	4 ms 5,760 KB
testcase_02	AC	3 ms 5,888 KB
testcase_03	AC	4 ms 5,888 KB
testcase_04	AC	4 ms 5,888 KB
testcase_05	AC	3 ms 5,888 KB
testcase_06	AC	3 ms 5,888 KB
testcase_07	AC	3 ms 6,016 KB
testcase_08	AC	3 ms 5,888 KB
testcase_09	AC	4 ms 5,760 KB
testcase_10	AC	3 ms 5,760 KB
testcase_11	AC	3 ms 5,888 KB
testcase_12	AC	3 ms 6,016 KB
testcase_13	AC	3 ms 5,760 KB
testcase_14	AC	101 ms 8,576 KB
testcase_15	AC	97 ms 8,320 KB
testcase_16	AC	186 ms 10,076 KB
testcase_17	AC	36 ms 6,940 KB
testcase_18	AC	186 ms 10,024 KB
testcase_19	AC	259 ms 11,460 KB
testcase_20	AC	14 ms 6,144 KB
testcase_21	AC	132 ms 8,832 KB
testcase_22	AC	178 ms 10,004 KB
testcase_23	AC	67 ms 7,452 KB
testcase_24	AC	259 ms 11,512 KB
testcase_25	AC	287 ms 11,380 KB
testcase_26	AC	276 ms 11,388 KB
testcase_27	AC	263 ms 11,380 KB
testcase_28	AC	269 ms 11,504 KB
testcase_29	AC	262 ms 11,536 KB
testcase_30	AC	279 ms 11,476 KB
testcase_31	AC	260 ms 11,332 KB
testcase_32	AC	283 ms 11,572 KB
testcase_33	AC	279 ms 11,392 KB
testcase_34	AC	44 ms 11,284 KB
testcase_35	AC	43 ms 11,284 KB
testcase_36	AC	45 ms 11,284 KB
testcase_37	AC	45 ms 11,284 KB
testcase_38	AC	45 ms 11,280 KB
testcase_39	AC	250 ms 15,724 KB
testcase_40	AC	247 ms 19,720 KB
testcase_41	AC	291 ms 16,436 KB
testcase_42	AC	277 ms 20,164 KB
testcase_43	AC	312 ms 17,608 KB
testcase_44	AC	78 ms 7,808 KB
testcase_45	AC	200 ms 10,808 KB
testcase_46	AC	96 ms 8,320 KB
testcase_47	AC	129 ms 9,076 KB
testcase_48	AC	51 ms 7,356 KB
testcase_49	AC	157 ms 9,576 KB
testcase_50	AC	142 ms 11,716 KB
testcase_51	AC	140 ms 11,520 KB
testcase_52	AC	143 ms 11,548 KB
testcase_53	AC	145 ms 11,728 KB
testcase_54	AC	141 ms 11,552 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=100005,INF=15<<26;

// BIT セグ木 遅延セグ木 のみ

// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)

#include <algorithm>
#include <array>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;

template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
                           std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <vector>

namespace atcoder {

template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;
    
public:
    fenwick_tree() : _n(0) {}
    fenwick_tree(int n) : _n(n), data(n) {}
    
    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }
    
    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }
    
private:
    int _n;
    std::vector<U> data;
    
    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder


#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
namespace atcoder {

template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    
    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }
    
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }
        
        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        
        return op(sml, smr);
    }
    
    S all_prod() { return d[1]; }
    
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        
        l += size;
        r += size;
        
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    
    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    
    S all_prod() { return d[1]; }
    
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
private:
    int _n, size, log;
    std::vector<S> d;
    
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder



//重心分解(使える版)

string S;
ll ans=0;

struct edge{
    int to;
    int length;
};

int N,C=-1;
vector<edge> G[MAX];

bool centroid[MAX];
int subtree_size[MAX];
int centpar[MAX];

int compute_subtree_size(int u,int p){
    int c=1;
    for(auto a:G[u]){
        if(a.to==p||centroid[a.to]) continue;
        c+=compute_subtree_size(a.to,u);
    }
    return subtree_size[u]=c;
}

pair<int,int> search_centroid(int u,int p,int t){
    pair<int,int> res={INF,-1};
    int s=1,m=0;
    for(auto a:G[u]){
        if(a.to==p||centroid[a.to]) continue;
        
        res=min(res,search_centroid(a.to,u,t));
        
        m=max(m,subtree_size[a.to]);
        s+=subtree_size[a.to];
    }
    m=max(m,t-s);
    res=min(res,{m,u});
    return res;
}

void enumerate_paths(int u,int p,int s,vector<int> &ds){
    if(S[u]=='1') s++;
    else s--;
    ds.push_back(s);
    for(auto a:G[u]){
        if(a.to==p||centroid[a.to]) continue;
        enumerate_paths(a.to,u,s,ds);
    }
}

void solve_subproblem(int u,int p){
    compute_subtree_size(u,-1);
    int D=subtree_size[u];
    int s=search_centroid(u,-1,subtree_size[u]).second;
    centroid[s]=1;
    if(C==-1) C=s;
    centpar[s]=p;
    
    for(auto a:G[s]){
        if(centroid[a.to]){
            continue;
        }
        solve_subproblem(a.to,s);
    }
    
    atcoder::fenwick_tree<int> BI(2*D+1);
    
    for(auto a:G[s]){
        if(centroid[a.to]) continue;
        
        vector<int> tds;
        enumerate_paths(a.to,s,0,tds);
        for(int x:tds){
            int need=x;
            if(S[s]=='1') need++;
            else need--;
            need=1-need;
            ans+=BI.sum(need+D,2*D+1);
        }
        for(int x:tds){
            BI.add(x+D,1);
        }
    }
    int need=0;
    if(S[s]=='1') need++;
    else need--;
    need=1-need;
    ans+=BI.sum(need+D,2*D+1);
    if(S[s]=='1') ans++;
    
    centroid[s]=0;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>N;
    for(int i=0;i<N-1;i++){
        int a,b;cin>>a>>b;a--;b--;
        G[a].push_back({b,1});
        G[b].push_back({a,1});
    }
    cin>>S;
    solve_subproblem(0,-1);
    
    cout<<ans<<endl;
}

yukicoder

結果

テストケース

ソースコード