結果

問題 No.1002 Twotone
ユーザー tko919tko919
提出日時 2020-05-29 16:07:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,042 bytes
コンパイル時間 2,092 ms
コンパイル使用メモリ 183,848 KB
実行使用メモリ 36,048 KB
最終ジャッジ日時 2024-10-15 12:56:05
合計ジャッジ時間 27,460 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
12,928 KB
testcase_01 AC 10 ms
12,800 KB
testcase_02 AC 19 ms
12,800 KB
testcase_03 AC 3,006 ms
22,104 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 AC 10 ms
12,800 KB
testcase_07 AC 2,363 ms
26,144 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
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> mp[201010],sum;
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;
         }
      }
      //cerr<<cen<<res<<endl;
   } 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