結果

問題 No.1002 Twotone
コンテスト
ユーザー tko919
提出日時 2020-05-29 16:14:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,992 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 183,924 KB
実行使用メモリ 78,336 KB
最終ジャッジ日時 2024-10-15 13:08:46
合計ジャッジ時間 9,554 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:35:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   35 |    for(auto [t,c]:g[cen])if(!used[t])rec(t);
      |             ^
main.cpp: In lambda function:
main.cpp:39:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   39 |          for(auto [t,c]:g[v])if(!used[t])dfs(t,v,++idx,{-1,c});
      |                   ^
main.cpp:43:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   43 |       for(auto [t,c]:g[v])if(t!=p and !used[t]){
      |                ^
main.cpp: In function 'void rec(int)':
main.cpp:64:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   64 |             auto [lb,rb]=equal_range(ALL(sum),p);
      |                  ^
main.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   66 |             auto [lb2,rb2]=equal_range(ALL(mp[i]),p);
      |                  ^
main.cpp:70:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   70 |             auto [lb3,rb3]=equal_range(ALL(sum),P{-1,a});
      |                  ^
main.cpp:72:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   72 |             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;
void rec(int rt){
   int cen=find(rt); used[cen]=1;
   for(auto [t,c]:g[cen])if(!used[t])rec(t);
   vector<P> mp[201010],sum;
   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