結果

問題 No.1002 Twotone
ユーザー tko919tko919
提出日時 2020-05-29 16:18:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,018 bytes
コンパイル時間 2,041 ms
コンパイル使用メモリ 192,040 KB
実行使用メモリ 51,712 KB
最終ジャッジ日時 2024-10-15 13:16:39
合計ジャッジ時間 28,789 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,320 KB
testcase_01 AC 5 ms
8,064 KB
testcase_02 AC 5 ms
8,064 KB
testcase_03 AC 273 ms
16,256 KB
testcase_04 AC 372 ms
18,560 KB
testcase_05 AC 376 ms
18,504 KB
testcase_06 AC 5 ms
8,160 KB
testcase_07 AC 1,129 ms
28,444 KB
testcase_08 AC 2,559 ms
45,812 KB
testcase_09 AC 2,596 ms
38,904 KB
testcase_10 AC 6 ms
8,064 KB
testcase_11 AC 1,582 ms
27,976 KB
testcase_12 AC 2,220 ms
31,832 KB
testcase_13 AC 2,005 ms
30,864 KB
testcase_14 AC 5 ms
8,192 KB
testcase_15 AC 1,098 ms
21,744 KB
testcase_16 AC 2,670 ms
31,684 KB
testcase_17 AC 2,232 ms
31,184 KB
testcase_18 AC 5 ms
8,260 KB
testcase_19 TLE -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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});
      |

ソースコード

diff # 

#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){
   vector<int> sz(n);
   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; map<int,vector<P>> mp;
void rec(int rt){
   int cen=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;
}
0