結果

問題 No.1002 Twotone
ユーザー tonegawatonegawa
提出日時 2021-02-21 17:25:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,170 ms / 5,000 ms
コード長 10,179 bytes
コンパイル時間 2,196 ms
コンパイル使用メモリ 179,684 KB
実行使用メモリ 73,600 KB
最終ジャッジ日時 2024-09-19 15:22:40
合計ジャッジ時間 32,395 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 594 ms
36,352 KB
testcase_04 AC 874 ms
46,464 KB
testcase_05 AC 861 ms
46,400 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 532 ms
29,440 KB
testcase_08 AC 1,042 ms
46,464 KB
testcase_09 AC 1,039 ms
46,464 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1,232 ms
36,992 KB
testcase_12 AC 1,838 ms
46,892 KB
testcase_13 AC 1,898 ms
46,876 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 762 ms
28,288 KB
testcase_16 AC 1,805 ms
46,848 KB
testcase_17 AC 1,900 ms
46,976 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1,103 ms
54,656 KB
testcase_20 AC 1,346 ms
73,600 KB
testcase_21 AC 1,399 ms
72,448 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 1,052 ms
40,960 KB
testcase_24 AC 2,162 ms
68,224 KB
testcase_25 AC 2,170 ms
64,364 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 194 ms
45,028 KB
testcase_28 AC 423 ms
57,180 KB
testcase_29 AC 332 ms
57,184 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 310 ms
56,824 KB
testcase_32 AC 427 ms
57,012 KB
testcase_33 AC 332 ms
56,968 KB
testcase_34 AC 1,801 ms
60,880 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from main.cpp:5:
In constructor 'constexpr std::_Head_base<_Idx, _Head, false>::_Head_base(_UHead&&) [with _UHead = int&; long unsigned int _Idx = 1; _Head = int]',
    inlined from 'constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = int&; _UTail = {std::vector<int, std::allocator<int> >&, std::vector<int, std::allocator<int> >&}; <template-parameter-2-3> = void; long unsigned int _Idx = 1; _Head = int; _Tail = {std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:292:38,
    inlined from 'constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = std::vector<std::vector<int> >&; _UTail = {int&, std::vector<int, std::allocator<int> >&, std::vector<int, std::allocator<int> >&}; <template-parameter-2-3> = void; long unsigned int _Idx = 0; _Head = std::vector<std::vector<int> >; _Tail = {int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:292:38,
    inlined from 'constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >&, int&, std::vector<int, std::allocator<int> >&, std::vector<int, std::allocator<int> >&}; bool _Valid = true; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = true; _Elements = {std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:744:54,
    inlined from 'std::tuple<std::vector<std::vector<int, std::allocator<int> >,

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#define all(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define bit_subset(i, S) for(int i=S, cnt=0;(cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x,y;i<(1<<n);x=(i&-i),y=i+x,i=(!i?(1<<n):((i&~y)/x>>1)|y))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
using ll = long long;
using ld = long double;
using ul = uint64_t;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
template<typename T>
bool mul_overflow(T a, T b){
  static T INF = numeric_limits<T>::max();
  return (INF / a) < b;
}
template<typename T>
bool add_overflow(T a, T b){
  static T INF = numeric_limits<T>::max();
  return (INF - a) < b;
}
template<typename T>
bool chmax(T &a, const T b){
  if(a >= b) return false;
  a = b;
  return true;
}
template<typename T>
bool chmin(T &a, const T b){
  if(a <= b) return false;
  a = b;
  return true;
}
template<typename T>
T max(vector<T> &v, int l=0, int r = -1){
  return *std::max_element(v.begin()+l, v.begin()+(r==-1?v.size():r));
}
template<typename T>
T min(vector<T> &v, int l=0, int r = -1){
  return *std::min_element(v.begin()+l, v.begin()+(r==-1?v.size():r));
}
template<typename T>
int argmax(vector<T> &v, int l=0, int r=-1){
  T res = max(v, l, r);
  if(r==-1) r = v.size();
  for(int i=l;i<r;i++) if(v[i]==res) return i;
  return -1;
}
template<typename T>
int argmin(vector<T> &v, int l=0, int r=-1){
  T res = min(v, l, r);
  if(r==-1) r = v.size();
  for(int i=l;i<r;i++) if(v[i]==res) return i;
  return -1;
}
ll gcd(ll _a, ll _b) {
  uint64_t a = abs(_a), b = abs(_b);
  if(a == 0) return b;
  if(b == 0) return a;
  int shift = __builtin_ctzll(a | b);
  a >>= __builtin_ctzll(a);
  do{
    b >>= __builtin_ctzll(b);
    if(a > b) std::swap(a, b);
    b -= a;
  }while(b);
  return (a << shift);
}
ll lcm(ll a, ll b){
  return (a / gcd(a, b)) * b;
}
ll llpow(ll a, ll b){
  ll ret = 1, mul = a;
  while(b){
    if(b&1) ret *= mul;
    mul *= mul;
    b >>= 1;
  }
  return ret;
}
template<int MOD>
ll mpow(ll a, ll b){
  int ret = (MOD==1?0:1), mul = a % MOD;
  while(b){
    if(b&1) ret = (ll(ret) * mul) % MOD;
    mul = (ll(mul) * mul) % MOD;
    b >>= 1;
  }
  return ret;
}
ll mpow(ll a, ll b, ll MOD){
  int ret = (MOD==1?0:1), mul = a % MOD;
  while(b){
    if(b&1) ret = (ll(ret) * mul) % MOD;
    mul = (ll(mul) * mul) % MOD;
    b >>= 1;
  }
  return ret;
}
int centroid_search(int now, int from, const vector<vector<int>> &G, const vector<bool> &is_centroid, vector<int> &size, int th, vector<int> &parent){
  int c = -1;
  parent[now] = from;
  size[now] = 1;
  for(int to:G[now]){
    if(to==from||is_centroid[to]) continue;
    int tmp_c = centroid_search(to, now, G, is_centroid, size, th, parent);
    size[now] += size[to];
    if(tmp_c!=-1) c = tmp_c;
  }
  if(c==-1&&size[now]>th) return now;
  return c;
}
tuple<vector<vector<int>>, int, vector<int>, vector<int>> centroid_decomposition(const vector<vector<int>> &G){
  int n = G.size(), root;
  vector<bool> is_centroid(n, false);
  vector<int> size(n), parent(n), depth(n), inner_parent(n);
  vector<vector<int>> g(n);
  queue<tuple<int, int, int>> q;
  q.push({0, -1, n});
  while(!q.empty()){
    auto [now, par, subtree_size] = q.front();
    q.pop();
    if(is_centroid[now]) continue;
    int c = centroid_search(now, -1, G, is_centroid, size, subtree_size/2, inner_parent);
    parent[c] = par;
    depth[c] = (par==-1?0:depth[par] + 1);
    if(par==-1) root = c;
    else g[par].push_back(c);
    is_centroid[c] = true;
    for(int to:G[c]){
      if(is_centroid[to]) continue;
      while(inner_parent[to]!=-1&&inner_parent[to]!=c) to = inner_parent[to];
      q.push({to, c, size[to]>size[c]?size[to]-size[c]:size[to]});
    }
  }
  return {g, root, parent, depth};
}

void map_set(unordered_map<ll, int> &mp, int a, int b, int c){
  if(b!=0&&a > b) swap(a, b);
  auto itr = mp.find(ll(a)*1000000+b);
  if(itr==mp.end()) mp.emplace(ll(a)*1000000+b, c);
  else itr->second = c;
}
void map_add(unordered_map<ll, int> &mp, int a, int b){
  if(b!=0&&a>b) swap(a, b);
  auto itr = mp.find(ll(a)*1000000+b);
  if(itr==mp.end()) mp.emplace(ll(a)*1000000+b, 1);
  else itr->second++;
}
int map_get(unordered_map<ll, int> &mp, int a, int b){
  if(b!=0&&a>b) swap(a, b);
  auto itr = mp.find(ll(a)*1000000+b);
  if(itr==mp.end()) return 0;
  return itr->second;
}

using pi = pair<int, int>;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  //各重心ノードcでv-cパスに含まれる色を持っておく
  //cでマージする時、同じ2色, 1色とその色を含む2色, 同じ1色をマージ
  int n, m;std::cin >> n >> m;
  vector<vector<int>> G(n);
  map<pi, int> color;
  range(i, 0, n-1){
    int a, b, c;std::cin >> a >> b >> c;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
    color.emplace(pi{min(a, b), max(a, b)}, c);
  }
  auto [g, root, parent, depth] = centroid_decomposition(G);
  //cから初めて色が2色以下の間探す
  ll ans = 0;
  ll add = 0;
  for(int i=0;i<n;i++){
    map<pi, int> ALL;
    ll O = 0;
    vector<map<pi, int>> subtree;
    vector<int> Ocount;
    for(int ch:G[i]){
      if(depth[ch]<=depth[i]) continue;
      subtree.push_back(map<pi, int>());
      Ocount.push_back(0);
      int idx = subtree.size() - 1;
      queue<tuple<int, int, int, int>> q;
      auto itr = color.find(pi{min(i, ch), max(i, ch)});
      q.push(tuple<int, int, int, int>{ch, i, itr->second, 0});
      while(!q.empty()){
        auto [now, from, c1, c2] = q.front();
        q.pop();
        if(c2==0){
          O++, Ocount[idx]++;
          itr = ALL.find(pi{c1, c2});
          if(itr==ALL.end()) ALL.emplace(pi{c1, c2}, 1);
          else itr->second++;
          itr = subtree[idx].find(pi{c1, c2});
          if(itr==subtree[idx].end()) subtree[idx].emplace(pi{c1, c2}, 1);
          else itr->second++;
        }else{
          itr = ALL.find(pi{min(c1, c2), max(c1, c2)});
          if(itr==ALL.end()) ALL.emplace(pi{min(c1, c2), max(c1, c2)}, 1);
          else itr->second++;
          itr = subtree[idx].find(pi{min(c1, c2), max(c1, c2)});
          if(itr==subtree[idx].end()) subtree[idx].emplace(pi{min(c1, c2), max(c1, c2)}, 1);
          else itr->second++;
        }
        for(auto nxt:G[now]){
          if(nxt==from||depth[nxt]<=depth[i]) continue;
          int ecolor = color.find(pi{min(now, nxt), max(now, nxt)})->second;
          if(c1==ecolor) q.push({nxt, now, c1, c2});
          else if(c2==0||c2==ecolor) q.push({nxt, now, c1, ecolor});
        }
      }
    }

    for(int j=0;j<subtree.size();j++){
      for(auto elem:subtree[j]){
        int c1 = elem.first.first;
        int c2 = elem.first.second;
        int count = elem.second;
        if(c2==0){
          auto itr = ALL.find(pi{c1, 0});
          int except_c1_all = O - (itr==ALL.end()?0:itr->second);
          itr = subtree[j].find(pi{c1, 0});
          int except_c1_j = Ocount[j] - (itr==subtree[j].end()?0:itr->second);
          ans += ll(except_c1_all - except_c1_j) * count;
        }else{
          auto itr = ALL.find(pi{min(c1, c2), max(c1, c2)});
          ans += count * 2;//2-0
          ans += ll((itr==ALL.end()?0:itr->second) - count) * count;

          itr = ALL.find(pi{c1, 0});
          int c1_all = (itr==ALL.end()?0:itr->second);
          itr = subtree[j].find(pi{c1, 0});
          int c1_j = (itr==subtree[j].end()?0:itr->second);
          itr = ALL.find(pi{c2, 0});
          int c2_all = (itr==ALL.end()?0:itr->second);
          itr = subtree[j].find(pi{c2, 0});
          int c2_j = (itr==subtree[j].end()?0:itr->second);
          add += ll(c1_all - c1_j) * count;
          add += ll(c2_all - c2_j) * count;
        }
      }
    }
  }
  //std::cout << add << '\n';
  std::cout << (ans / 2) + add << '\n';
}
0