結果
問題 | No.1002 Twotone |
ユーザー | 沙耶花 |
提出日時 | 2021-03-04 22:52:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,849 ms / 5,000 ms |
コード長 | 6,177 bytes |
コンパイル時間 | 3,667 ms |
コンパイル使用メモリ | 256,508 KB |
実行使用メモリ | 214,048 KB |
最終ジャッジ日時 | 2024-10-05 12:25:48 |
合計ジャッジ時間 | 33,966 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 1,130 ms
134,032 KB |
testcase_04 | AC | 1,522 ms
173,696 KB |
testcase_05 | AC | 1,508 ms
173,676 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 575 ms
104,184 KB |
testcase_08 | AC | 1,043 ms
173,728 KB |
testcase_09 | AC | 1,075 ms
173,556 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 1,210 ms
134,300 KB |
testcase_12 | AC | 1,745 ms
173,028 KB |
testcase_13 | AC | 1,825 ms
172,976 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 838 ms
97,924 KB |
testcase_16 | AC | 1,741 ms
172,884 KB |
testcase_17 | AC | 1,849 ms
172,944 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 1,482 ms
170,592 KB |
testcase_20 | AC | 1,580 ms
214,048 KB |
testcase_21 | AC | 1,550 ms
212,048 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 856 ms
123,192 KB |
testcase_24 | AC | 1,576 ms
205,336 KB |
testcase_25 | AC | 1,469 ms
198,828 KB |
testcase_26 | AC | 2 ms
6,816 KB |
testcase_27 | AC | 286 ms
116,960 KB |
testcase_28 | AC | 534 ms
173,748 KB |
testcase_29 | AC | 470 ms
173,736 KB |
testcase_30 | AC | 2 ms
6,820 KB |
testcase_31 | AC | 377 ms
172,928 KB |
testcase_32 | AC | 482 ms
173,768 KB |
testcase_33 | AC | 402 ms
173,828 KB |
testcase_34 | AC | 1,144 ms
196,888 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 struct Data{ array<int,3> a; Data(){ rep(i,3)a[i] = Inf; } void add(int x){ if(x==Inf)return; rep(i,3){ if(a[i]==x)return; } rep(i,3){ if(a[i]==Inf){ a[i] = x; break; } } sort(a.begin(),a.end()); } }; template <class S, S (*op)(S, S), S (*e)()> struct sparse_table{ vector<S> v; int _n; int sz; sparse_table() : sparse_table(0) {} sparse_table(int n) : sparse_table(std::vector<S>(n, e())) {} sparse_table(const std::vector<S>& x) : _n(int(x.size())) { sz = x.size(); for(int i=0;true;i++){ if((1<<i)>_n){ sz = i; break; } } v.resize(sz*_n,e()); for(int i=0;i<_n;i++){ v[i] = x[i]; } for(int i=1;i<sz;i++){ for(int j=0;j<_n+1-(1<<i);j++){ int temp = j+(1<<(i-1)); v[i*_n+j] = op(v[(i-1)*_n+j],v[(i-1)*_n+temp]); } } } S prod(int l,int r){ int x = 31-__builtin_clz(r-l); return op(v[_n*x+l],v[_n*x+r-(1<<x)]); } }; struct centroid_tree{ vector<vector<int>> E; vector<int> cnt; int r; vector<int> pos; vector<vector<int>> bind; vector<int> ind; vector<pair<int,int>> par; centroid_tree(vector<vector<int>> argE){ int n = argE.size(); E.resize(n,vector<int>()); cnt.resize(n); r = go(0,argE); pos.resize(n); bind.resize(n); par.resize(n,make_pair(-1,-1)); dfs(r,-1,E); build(r,0); } int go(int a,vector<vector<int>> &argE){ dfs(a,-1,argE); int sz = cnt[a]; int ret = dfs2(a,-1,argE,sz); rep(i,argE[ret].size()){ int to = argE[ret][i]; argE[to].erase(find(argE[to].begin(),argE[to].end(),ret)); int g = go(to,argE); E[ret].push_back(g); } argE[ret].clear(); return ret; } void dfs(int cur,int p,vector<vector<int>> &argE){ cnt[cur] = 1; rep(i,argE[cur].size()){ int to = argE[cur][i]; if(to==p)continue; dfs(to,cur,argE); cnt[cur] += cnt[to]; } } int dfs2(int cur,int p,vector<vector<int>> &argE,int sz){ int ret = -1; int m = 0; rep(i,argE[cur].size()){ int to = argE[cur][i]; if(to==p)continue; ret = dfs2(to,cur,argE,sz); if(ret!=-1)return ret; m = max(m,cnt[to]); } if(sz-cnt[cur]<=sz/2 && m<=sz/2){ ret = cur; } return ret; } void build(int cur,int d){ int x = cur; pos[cur] = ind.size(); bind[cur].push_back(ind.size()); ind.push_back(cur); rep(i,E[cur].size()){ int to = E[cur][i]; int x = to; bind[cur].push_back(ind.size()); par[to] = make_pair(cur,i+1); build(to,d+1); } bind[cur].push_back(ind.size()); } }; struct HLD{ vector<int> sz,parent,depth,root,pos; vector<int> arr; HLD(vector<vector<int>> &E){ sz.resize(E.size(),1); parent.resize(E.size(),0); depth.resize(E.size(),0); root.resize(E.size(),0); pos.resize(E.size(),0); dfs(0,-1,E); dfs2(0,-1,E,0); } void dfs(int now,int p,vector<vector<int>> &E){ parent[now] = p; if(p==-1){ depth[now] = 0; } else{ depth[now] = depth[p]+1; } for(int i=0;i<E[now].size();i++){ int to = E[now][i]; if(to==p)continue; dfs(to,now,E); sz[now] += sz[to]; } } void dfs2(int now,int p,vector<vector<int>> &E,int r){ pos[now] = arr.size(); arr.push_back(now); root[now] = r; int maxi = 0; int ind = -1; for(int i=0;i<E[now].size();i++){ int to = E[now][i]; if(to==p)continue; if(maxi<sz[to]){ maxi = sz[to]; ind = to; } } if(ind==-1)return; dfs2(ind,now,E,r); for(int i=0;i<E[now].size();i++){ int to = E[now][i]; if(to==p||to==ind)continue; dfs2(to,now,E,to); } } vector<pair<int,int>> query(int u,int v){ vector<pair<int,int>> ret; int t = 0; while(root[u]!=root[v]){ if(depth[root[u]] <= depth[root[v]]){ ret.insert(ret.begin()+t,{pos[root[v]], pos[v]}); v = parent[root[v]]; } else{ ret.insert(ret.begin()+t,{pos[u],pos[root[u]]}); u = parent[root[u]]; t++; } } ret.insert(ret.begin()+t,{pos[u],pos[v]}); return ret; } int lca(int u,int v){ for(;;v=parent[root[v]]){ if(pos[u]>pos[v])swap(u,v); if(root[u]==root[v])return u; } } int get_distance(int u,int v){ return depth[u] + depth[v] - 2 * depth[lca(u,v)]; } }; Data op(Data a,Data b){ rep(i,3){ a.add(b.a[i]); } return a; } Data e(){ return Data(); } int main(){ int n,k; cin>>n>>k; vector<Data> D(2*n-1); vector<vector<int>> E(n); vector<vector<int>> E2(2*n-1); rep(i,n-1){ int u,v,c; scanf("%d %d %d",&u,&v,&c); u--;v--;c--; E[u].push_back(v); E[v].push_back(u); E2[u].push_back(n+i); E2[v].push_back(n+i); E2[n+i].push_back(u); E2[n+i].push_back(v); D[n+i].add(c); } HLD H(E2); { vector<Data> D2(2*n-1); rep(i,2*n-1){ D2[H.pos[i]] = D[i]; } swap(D,D2); } centroid_tree C(E); sparse_table<Data,op,e> seg(D); long long ans = 0LL; rep(i,n){ long long cnt1all = 0LL; map<int,long long> cnt1,cnt2; map<pair<int,int>,long long> cntp; long long I = 0LL; rep(j,C.bind[i].size()-1){ vector<Data> V; for(int k=C.bind[i][j];k<C.bind[i][j+1];k++){ auto r = H.query(i,C.ind[k]); Data t; rep(l,r.size()){ int a = r[l].first,b = r[l].second; if(a>b)swap(a,b); t = op(t,seg.prod(a,b+1)); } V.push_back(t); } rep(k,V.size()){ if(V[k].a[0]==Inf)continue; if(V[k].a.back()!=Inf)continue; if(V[k].a[1]==Inf){ int x = V[k].a[0]; ans += cnt1all; if(cnt1.count(x))ans -= cnt1[x]; if(cnt2.count(x))ans += cnt2[x]; } else{ int x = V[k].a[0],y = V[k].a[1]; ans += I; if(cnt1.count(x))ans += cnt1[x]; if(cnt1.count(y))ans += cnt1[y]; if(cntp.count(make_pair(x,y)))ans += cntp[make_pair(x,y)]; } } rep(k,V.size()){ if(V[k].a[0]==Inf){ I++; continue; } if(V[k].a.back()!=Inf)continue; if(V[k].a[1]==Inf){ int x = V[k].a[0]; cnt1[x]++; cnt1all++; } else{ int x = V[k].a[0],y = V[k].a[1]; cnt2[x]++; cnt2[y]++; cntp[make_pair(x,y)]++; } } } } cout<<ans<<endl; return 0; }