結果
| 問題 | No.1002 Twotone |
| ユーザー |
 tko919
|
| 提出日時 | 2020-05-29 16:19:45 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,437 ms / 5,000 ms |
| コード長 | 3,042 bytes |
| コンパイル時間 | 2,068 ms |
| コンパイル使用メモリ | 191,356 KB |
| 実行使用メモリ | 46,392 KB |
| 最終ジャッジ日時 | 2024-04-23 13:21:06 |
| 合計ジャッジ時間 | 35,082 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
8,340 KB |
| testcase_01 | AC | 3 ms
8,288 KB |
| testcase_02 | AC | 3 ms
8,212 KB |
| testcase_03 | AC | 592 ms
21,972 KB |
| testcase_04 | AC | 809 ms
27,756 KB |
| testcase_05 | AC | 816 ms
27,624 KB |
| testcase_06 | AC | 5 ms
8,276 KB |
| testcase_07 | AC | 693 ms
22,012 KB |
| testcase_08 | AC | 1,317 ms
33,180 KB |
| testcase_09 | AC | 1,302 ms
34,220 KB |
| testcase_10 | AC | 4 ms
8,296 KB |
| testcase_11 | AC | 1,413 ms
25,776 KB |
| testcase_12 | AC | 1,930 ms
30,532 KB |
| testcase_13 | AC | 1,966 ms
29,040 KB |
| testcase_14 | AC | 4 ms
8,336 KB |
| testcase_15 | AC | 1,020 ms
20,332 KB |
| testcase_16 | AC | 2,023 ms
30,576 KB |
| testcase_17 | AC | 1,974 ms
30,200 KB |
| testcase_18 | AC | 5 ms
8,308 KB |
| testcase_19 | AC | 1,338 ms
32,368 KB |
| testcase_20 | AC | 1,673 ms
45,068 KB |
| testcase_21 | AC | 1,667 ms
44,172 KB |
| testcase_22 | AC | 5 ms
8,296 KB |
| testcase_23 | AC | 1,322 ms
30,844 KB |
| testcase_24 | AC | 2,437 ms
46,384 KB |
| testcase_25 | AC | 2,391 ms
46,392 KB |
| testcase_26 | AC | 4 ms
8,304 KB |
| testcase_27 | AC | 237 ms
30,596 KB |
| testcase_28 | AC | 403 ms
39,156 KB |
| testcase_29 | AC | 396 ms
39,024 KB |
| testcase_30 | AC | 4 ms
8,272 KB |
| testcase_31 | AC | 383 ms
38,808 KB |
| testcase_32 | AC | 436 ms
39,156 KB |
| testcase_33 | AC | 399 ms
39,088 KB |
| testcase_34 | AC | 1,691 ms
41,244 KB |
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:20:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
20 | for(auto [t,c]:g[v])if(t!=p and !used[t]){
| ^
main.cpp: In lambda function:
main.cpp:25:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
25 | for(auto [t,c]:g[v])if(t!=p and !used[t]){
| ^
main.cpp: In function 'void rec(int)':
main.cpp:36:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
36 | for(auto [t,c]:g[cen])if(!used[t])rec(t);
| ^
main.cpp: In lambda function:
main.cpp:40:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
40 | for(auto [t,c]:g[v])if(!used[t])dfs(t,v,++idx,{-1,c});
| ^
main.cpp:44:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
44 | for(auto [t,c]:g[v])if(t!=p and !used[t]){
| ^
main.cpp: In function 'void rec(int)':
main.cpp:65:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
65 | auto [lb,rb]=equal_range(ALL(sum),p);
| ^
main.cpp:67:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
67 | auto [lb2,rb2]=equal_range(ALL(mp[i]),p);
| ^
main.cpp:71:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
71 | auto [lb3,rb3]=equal_range(ALL(sum),P{-1,a});
| ^
main.cpp:73:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
73 | auto [lb4,rb4]=equal_range(ALL(mp[i]),P{-1,a});
|
ソースコード
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end
typedef pair<ll,ll> P;
int n,k; vector<P> g[201010]; bool used[201010]={};
int find(int rt){
unordered_map<int,int> sz;
function<void(int,int)> get=[&](int v,int p){
sz[v]=1;
for(auto [t,c]:g[v])if(t!=p and !used[t]){
get(t,v); sz[v]+=sz[t];
}
};
function<int(int,int)> dfs=[&](int v,int p){
for(auto [t,c]:g[v])if(t!=p and !used[t]){
if(sz[t]>sz[rt]/2)return dfs(t,v);
} return v;
};
get(rt,-1); return dfs(rt,-1);
}
ll res=0;
vector<P> sum; unordered_map<int,vector<P>> mp;
void rec(int rt){
int cen=find(rt); used[cen]=1;
for(auto [t,c]:g[cen])if(!used[t])rec(t);
rep(i,0,g[cen].size())mp[i].clear(); sum.clear();
function<void(int,int,int,P)> dfs=[&](int v,int p,int idx,P col){
if(idx==-1){
for(auto [t,c]:g[v])if(!used[t])dfs(t,v,++idx,{-1,c});
return;
}
mp[idx].push_back(col); sum.push_back(col);
for(auto [t,c]:g[v])if(t!=p and !used[t]){
P nxt=col;
if(col.first!=-1){
if(col.first!=c and col.second!=c)continue;
}
else{
if(col.second!=c)nxt=minmax(col.second,c);
} dfs(t,v,idx,nxt);
}
};
dfs(cen,-1,-1,{-1,-1});
sort(ALL(sum));
rep(i,0,g[cen].size()){
sort(ALL(mp[i]));
for(auto p:mp[i]){
int a=p.first,b=p.second;
if(a!=-1 and b!=-1){
//{-1,-1}
res+=2;
//{a,b}
auto [lb,rb]=equal_range(ALL(sum),p);
res+=rb-lb;
auto [lb2,rb2]=equal_range(ALL(mp[i]),p);
res-=rb2-lb2;
//{-1,a}
auto [lb3,rb3]=equal_range(ALL(sum),P{-1,a});
res+=2*(rb3-lb3);
auto [lb4,rb4]=equal_range(ALL(mp[i]),P{-1,a});
res-=2*(rb4-lb4);
//{-1,b}
auto [lb5,rb5]=equal_range(ALL(sum),P{-1,b});
res+=2*(rb5-lb5);
auto [lb6,rb6]=equal_range(ALL(mp[i]),P{-1,b});
res-=2*(rb6-lb6);
}
else{
//{-1,b},{a,b}
res+=upper_bound(ALL(sum),P{-1,INF})-lower_bound(ALL(sum),P{-1,0});
auto [lb,rb]=equal_range(ALL(sum),p); res-=rb-lb;
res-=upper_bound(ALL(mp[i]),P{-1,INF})-lower_bound(ALL(mp[i]),P{-1,0});
auto [lb2,rb2]=equal_range(ALL(mp[i]),p); res+=rb2-lb2;
}
}
} used[cen]=0;
}
int main(){
cin>>n>>k;
rep(_,0,n-1){
int x,y,z; cin>>x>>y>>z; x--; y--;
g[x].push_back({y,z}); g[y].push_back({x,z});
}
rec(0); cout<<res/2<<endl;
return 0;
}