結果
| 問題 | No.1002 Twotone |
| ユーザー |
 tonegawa
|
| 提出日時 | 2021-02-21 18:09:58 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 4,033 ms / 5,000 ms |
| コード長 | 14,351 bytes |
| コンパイル時間 | 2,016 ms |
| コンパイル使用メモリ | 165,352 KB |
| 実行使用メモリ | 498,960 KB |
| 最終ジャッジ日時 | 2024-09-19 16:00:07 |
| 合計ジャッジ時間 | 50,582 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 936 ms
126,652 KB |
| testcase_04 | AC | 1,290 ms
163,904 KB |
| testcase_05 | AC | 1,385 ms
163,904 KB |
| testcase_06 | AC | 2 ms
6,940 KB |
| testcase_07 | AC | 718 ms
67,704 KB |
| testcase_08 | AC | 1,307 ms
109,140 KB |
| testcase_09 | AC | 1,371 ms
109,140 KB |
| testcase_10 | AC | 2 ms
6,940 KB |
| testcase_11 | AC | 1,944 ms
91,904 KB |
| testcase_12 | AC | 2,761 ms
117,948 KB |
| testcase_13 | AC | 2,871 ms
117,952 KB |
| testcase_14 | AC | 2 ms
6,940 KB |
| testcase_15 | AC | 1,171 ms
72,192 KB |
| testcase_16 | AC | 2,949 ms
123,620 KB |
| testcase_17 | AC | 2,960 ms
123,584 KB |
| testcase_18 | AC | 2 ms
6,944 KB |
| testcase_19 | AC | 2,119 ms
114,520 KB |
| testcase_20 | AC | 2,458 ms
143,604 KB |
| testcase_21 | AC | 2,446 ms
142,408 KB |
| testcase_22 | AC | 2 ms
6,944 KB |
| testcase_23 | AC | 1,752 ms
89,320 KB |
| testcase_24 | AC | 3,664 ms
148,040 KB |
| testcase_25 | AC | 3,515 ms
144,112 KB |
| testcase_26 | AC | 2 ms
6,944 KB |
| testcase_27 | AC | 394 ms
67,580 KB |
| testcase_28 | AC | 800 ms
97,156 KB |
| testcase_29 | AC | 674 ms
97,292 KB |
| testcase_30 | AC | 2 ms
6,940 KB |
| testcase_31 | AC | 666 ms
96,488 KB |
| testcase_32 | AC | 779 ms
96,964 KB |
| testcase_33 | AC | 675 ms
97,152 KB |
| testcase_34 | AC | 4,033 ms
498,960 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> >,
ソースコード
#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};
}
template<typename K, typename T>
struct rbtree_map{
private:
struct node{
K key;
int red, sz;
T val;
node *par, *ch[2];
node(): red(0), sz(0){}
node(K key, T val):key(key), red(1), sz(1), val(val){
par = ch[0] = ch[1] = nullptr;
}
};
inline void eval(node *v){
if(v==nil) return;
v->sz = 1 + v->ch[0]->sz + v->ch[1]->sz;
}
void rec_eval(node *v){
if(v==nil) v = v->par;
while(v!=nil){
eval(v);
v = v->par;
}
}
void rotate(node *x, int d){
int e = d^1;
node *y = x->ch[e];
x->ch[e] = y->ch[d];
eval(x);
if(y->ch[d]!=nil) y->ch[d]->par = x;
y->par = x->par;
if(x->par==nil) root = y;
else if(x==x->par->ch[d]) x->par->ch[d] = y, eval(x->par);
else x->par->ch[e] = y, eval(x->par);
y->ch[d] = x;
eval(y);
x->par = y;
}
node *minimum(node* x){
while(x->ch[0]!=nil) x = x->ch[0];
return x;
}
void transplant(node *u, node *v){
if(u->par==nil) root = v;
else if(u==u->par->ch[0]) u->par->ch[0] = v;
else u->par->ch[1] = v;
v->par = u->par;
}
void insert_update(node *z){
node *y;
while(z->par->red){
int d = (z->par==z->par->par->ch[0]?0:1), e = d^1;
y = z->par->par->ch[e];
if(y->red){
z->par->red = 0;
y->red = 0;
z->par->par->red = 1;
z = z->par->par;
}else if(z==z->par->ch[e]){
z = z->par;
rotate(z,d);
}else{
z->par->red = 0;
z->par->par->red = 1;
rotate(z->par->par,e);
}
}
root->red = 0;
}
node *build(int l, int r, int d, node *parent, const vector<pair<K, T>> &v){
int mid = (r+l)/2;
node *now = new node(v[mid].first, v[mid].second);
now->red = d;
now->par = parent;
if(mid>l) now->ch[0] = build(l, mid, d^1, now, v);
else now->ch[0] = nil;
if(r>mid+1) now->ch[1] = build(mid+1, r, d^1, now, v);
else now->ch[1] = nil;
eval(now);
return now;
}
public:
node *root, *nil;
rbtree_map(){
nil = new node();
root = nil->par = nil->ch[0] = nil->ch[1] = nil;
}
rbtree_map(vector<pair<K, T>> v){
nil = new node();
sort(v.begin(), v.end());
root = build(0, v.size(), 0, nil, v);
}
void print(){
print(root, 0, 0);
}
int size(){
return root->sz;
}
node *find(K key){
node *x = root;
while(x != nil){
if(key != x->key) x = x->ch[key > x->key];
else return x;
}
return x;
}
node *insert(K key, T val){
node *x = root, *y = nil;
while(x!=nil){
y = x;
if(key != x->key) x = x->ch[key > x->key];
else return x;
}
node *z = new node(key, val);
z->par = y;
if(y==nil) root = z;
else y->ch[z->key >= y->key] = z, eval(y);
z->ch[0] = z->ch[1] = nil;
insert_update(z);
nil->par = nil->ch[0] = nil->ch[1] = nil;
rec_eval(z);
return z;
}
void erase(node *z){
if(z==nil) return;
node *y = z, *x;
int prevy = y->red;
if(z->ch[0]==nil){
x = z->ch[1];
transplant(z, z->ch[1]);
rec_eval(x);
}else if(z->ch[1]==nil){
x = z->ch[0];
transplant(z, z->ch[0]);
rec_eval(x);
}else{
y = minimum(z->ch[1]);
prevy = y->red;
x = y->ch[1];
if(y->par==z){
x->par = y;
transplant(z, y);
y->ch[0] = z->ch[0];
y->ch[0]->par = y;
y->red = z->red;
rec_eval(y);
}else{
transplant(y, y->ch[1]);
node *tmp = y->par;
y->ch[1] = z->ch[1];
y->ch[1]->par = y;
transplant(z, y);
y->ch[0] = z->ch[0];
y->ch[0]->par = y;
y->red = z->red;
rec_eval(tmp);
}
}
if(!prevy) x->red = 0;
delete z;
nil->par = nil->ch[0] = nil->ch[1] = nil;
}
void erase(K key){
erase(find(key));
}
node *lower_bound(K key){
node *x = root, *y;
while(x != nil){
if(x->key>=key) y = x;
if(key != x->key) x = x->ch[key > x->key];
else return x;
}
return y;
}
node *upper_bound(K key){
node *x = root, *y;
while(x != nil){
if(x->key>key) y = x;
x = x->ch[key >= x->key];
}
return y;
}
node *reverse_lower_bound(K key){
node *x = root, *y;
while(x != nil){
if(x->key<=key) y = x;
if(key != x->key) x = x->ch[key > x->key];
else return x;
}
return y;
}
node *reverse_upper_bound(K key){
node *x = root, *y;
while(x != nil){
if(x->key<key) y = x;
x = x->ch[key > x->key];
}
return y;
}
int under_count(K key){
node *x = root;
int ret = 0;
while(x != nil){
if(x->key<=key) ret += (x->key!=key) + x->ch[0]->sz;
if(key != x->key) x = x->ch[key > x->key];
else return ret;
}
return ret;
}
node *kth_element(int k){
if(root->sz<=k) return nil;
node *x = root;
while(x!=nil){
int lsz = x->ch[0]->sz;
if(k==lsz) return x;
if(lsz<k) k -= lsz + 1, x = x->ch[1];
else x = x->ch[0];
}
return nil;
}
};
int main(){
auto set_map = [](rbtree_map<ll, int> &mp, int a, int b, int c)->void{
auto node = mp.find(ll(a)*1000000000+b);
if(node==mp.nil) mp.insert(ll(a)*1000000000+b, c);
};
auto add_map = [](rbtree_map<ll, int> &mp, int a, int b, int c)->void{
auto node = mp.find(ll(a)*1000000000+b);
if(node==mp.nil) mp.insert(ll(a)*1000000000+b, c);
else node->val += c;
};
auto get_map = [](rbtree_map<ll, int> &mp, int a, int b)->int{
auto node = mp.find(ll(a)*1000000000 + b);
if(node==mp.nil) return 0;
return node->val;
};
//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);
rbtree_map<ll, 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);
set_map(color, a, b, c);
set_map(color, b, a, c);
}
auto [g, root, parent, depth] = centroid_decomposition(G);
//cから初めて色が2色以下の間探す
ll ans = 0;
ll add = 0;
for(int i=0;i<n;i++){
rbtree_map<ll, int> ALL;
ll O = 0;
vector<rbtree_map<ll, int>> subtree;
vector<int> Ocount;
for(int ch:G[i]){
if(depth[ch]<=depth[i]) continue;
subtree.push_back(rbtree_map<ll, int>());
Ocount.push_back(0);
int idx = subtree.size() - 1;
queue<tuple<int, int, int, int>> q;
q.push(tuple<int, int, int, int>{ch, i, get_map(color, i, ch), 0});
while(!q.empty()){
auto [now, from, c1, c2] = q.front();
q.pop();
if(c2==0) O++, Ocount[idx]++;
add_map(ALL, c1, c2, 1);
add_map(ALL, c2, c1, 1);
add_map(subtree[idx], c1, c2, 1);
add_map(subtree[idx], c2, c1, 1);
for(auto nxt:G[now]){
if(nxt==from||depth[nxt]<=depth[i]) continue;
int ecolor = get_map(color, now, nxt);
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(int t=0;t<subtree[j].size();t++){
auto itr = subtree[j].kth_element(t);
int c1 = itr->key / 1000000000;
int c2 = itr->key % 1000000000;
if(c1==0||c1<c2) continue;
int count = itr->val;
if(c2==0){
int except_c1_all = O - get_map(ALL, c1, c2);
int except_c1_j = Ocount[j] - get_map(subtree[j], c1, c2);
ans += ll(except_c1_all - except_c1_j) * count;
}else{
ans += count * 2;//2-0
ans += ll(get_map(ALL, c1, c2) - count) * count;
int c1_all = get_map(ALL, c1, 0);
int c1_j = get_map(subtree[j], c1, 0);
int c2_all = get_map(ALL, c2, 0);
int c2_j = get_map(subtree[j], c2, 0);
add += ll(c1_all - c1_j) * count;
add += ll(c2_all - c2_j) * count;
}
}
}
}
//std::cout << add << '\n';
std::cout << (ans / 2) + add << '\n';
}