結果
問題 | No.2892 Lime and Karin |
ユーザー | GOTKAKO |
提出日時 | 2024-09-14 00:56:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 215 ms / 8,000 ms |
コード長 | 6,270 bytes |
コンパイル時間 | 2,634 ms |
コンパイル使用メモリ | 214,960 KB |
実行使用メモリ | 38,912 KB |
最終ジャッジ日時 | 2024-09-14 00:56:41 |
合計ジャッジ時間 | 9,297 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 3 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 68 ms
7,168 KB |
testcase_15 | AC | 63 ms
7,424 KB |
testcase_16 | AC | 119 ms
9,984 KB |
testcase_17 | AC | 23 ms
6,940 KB |
testcase_18 | AC | 109 ms
9,984 KB |
testcase_19 | AC | 179 ms
11,392 KB |
testcase_20 | AC | 9 ms
6,944 KB |
testcase_21 | AC | 82 ms
7,808 KB |
testcase_22 | AC | 118 ms
9,856 KB |
testcase_23 | AC | 41 ms
6,940 KB |
testcase_24 | AC | 168 ms
11,648 KB |
testcase_25 | AC | 176 ms
11,520 KB |
testcase_26 | AC | 181 ms
11,392 KB |
testcase_27 | AC | 182 ms
11,520 KB |
testcase_28 | AC | 215 ms
11,520 KB |
testcase_29 | AC | 170 ms
11,520 KB |
testcase_30 | AC | 176 ms
11,520 KB |
testcase_31 | AC | 186 ms
11,520 KB |
testcase_32 | AC | 177 ms
11,520 KB |
testcase_33 | AC | 179 ms
11,528 KB |
testcase_34 | AC | 58 ms
11,796 KB |
testcase_35 | AC | 58 ms
11,660 KB |
testcase_36 | AC | 60 ms
11,788 KB |
testcase_37 | AC | 59 ms
11,664 KB |
testcase_38 | AC | 60 ms
11,792 KB |
testcase_39 | AC | 105 ms
25,600 KB |
testcase_40 | AC | 108 ms
37,504 KB |
testcase_41 | AC | 118 ms
27,648 KB |
testcase_42 | AC | 104 ms
38,912 KB |
testcase_43 | AC | 101 ms
31,232 KB |
testcase_44 | AC | 49 ms
6,940 KB |
testcase_45 | AC | 140 ms
10,752 KB |
testcase_46 | AC | 63 ms
7,168 KB |
testcase_47 | AC | 75 ms
8,192 KB |
testcase_48 | AC | 32 ms
6,940 KB |
testcase_49 | AC | 104 ms
9,600 KB |
testcase_50 | AC | 114 ms
11,520 KB |
testcase_51 | AC | 109 ms
11,776 KB |
testcase_52 | AC | 123 ms
11,776 KB |
testcase_53 | AC | 120 ms
11,648 KB |
testcase_54 | AC | 122 ms
11,648 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using SS = int; class SegmentTree{ public: int siz = 1,n; vector<SS> dat; SS op(SS a, SS b){return a+b;} SS e(){return 0;} void renew (SS &a,SS x){ a = op(a,x); //a = x; //その他. } void make(int N){ while(siz < N) siz *= 2; n = N; dat.resize(siz*2,e()); } void make2(int N,vector<SS> &A){ make(N); for(int i=0; i<N; i++){ int pos = i+siz; dat.at(pos) = A.at(i); } for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void update(int pos,SS x){ pos = pos+siz; renew(dat.at(pos),x); while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } SS findans(int l, int r){ SS retl = e(),retr = e(); l += siz,r += siz; while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS get(int pos){return dat.at(pos+siz);} SS rangeans(int l, int r){return findans(l,r);} SS allrange(){return dat.at(1);} //rightは) leftは[で 渡す&返す. int maxright(const function<bool(SS)> f,int l = 0){ l += siz; int r = n+siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okl = e(); for(int i=0; i<ls.size(); i++){ l = ls.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } for(int i=rs.size()-1; i>=0; i--){ l = rs.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } return n; } int minleft(const function<bool(SS)> f,int r = -1){ if(r == -1) r = n; int l = siz; r += siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okr = e(); for(int i=0; i<rs.size(); i++){ r = rs.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } for(int i=ls.size()-1; i>=0; i--){ r = ls.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } return 0; } //ノーマルセグ木.一年の時を経て漸く二分探索実装した. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<vector<int>> Graph(N); for(int i=0; i<N-1; i++){ int u,v; cin >> u >> v; u--; v--; Graph.at(u).push_back(v); Graph.at(v).push_back(u); } vector<int> siz(N); { auto dfs = [&](auto dfs,int pos,int back) -> int { int ret = 1; for(auto to : Graph.at(pos)) if(to != back) ret += dfs(dfs,to,pos); siz.at(pos) = ret; return ret; }; dfs(dfs,0,-1); } for(auto &g : Graph) sort(g.begin(),g.end(),[&](auto &a,auto &b){return siz.at(a)>siz.at(b);}); SegmentTree Z; Z.make(N*2+9); int zero = N+4; long long answer = 0; string s; cin >> s; auto dfs = [&](auto dfs,int pos,int back) -> int { int maxs = 0,big = -1; for(auto to : Graph.at(pos)) if(to != back && maxs < siz.at(to)) maxs = siz.at(to),big = to; for(auto to : Graph.at(pos)){ if(to == back || to == big) continue; int n = dfs(dfs,to,pos); auto dfs2 = [&](auto dfs2,int pos,int back) -> void { if(s.at(pos) == '1') n++; else n--; Z.update(n,-1); for(auto to : Graph.at(pos)) if(to != back) dfs2(dfs2,to,pos); if(s.at(pos) == '1') n--; else n++; }; dfs2(dfs2,to,pos); } { int n = zero; if(big != -1) n = dfs(dfs,big,pos); Z.update(n,1); if(s.at(pos) == '1') n--; else n++; answer += Z.rangeans(n+1,Z.siz); auto dfs2 = [&](auto dfs2,int pos,int back) -> void { if(s.at(pos) == '1') n--; else n++; answer += Z.rangeans(n+1,Z.siz); for(auto to : Graph.at(pos)) if(to != back) dfs2(dfs2,to,pos); if(s.at(pos) == '1') n++; else n--; }; auto dfs3 = [&](auto dfs3,int pos,int back) -> void { if(s.at(pos) == '1') n++; else n--; Z.update(n,1); for(auto to : Graph.at(pos)) if(to != back) dfs3(dfs3,to,pos); if(s.at(pos) == '1') n--; else n++; }; for(auto to : Graph.at(pos)){ if(to == back || to == big) continue; dfs2(dfs2,to,pos); if(s.at(pos) == '1') n++; else n--; dfs3(dfs3,to,pos); if(s.at(pos) == '1') n--; else n++; } return n; } }; dfs(dfs,0,-1); cout << answer << endl; }