結果
| 問題 | No.1002 Twotone |
| ユーザー |
 tsutaj
|
| 提出日時 | 2020-02-21 01:40:10 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,513 bytes |
| コンパイル時間 | 796 ms |
| コンパイル使用メモリ | 68,864 KB |
| 実行使用メモリ | 57,924 KB |
| 最終ジャッジ日時 | 2024-04-18 08:29:20 |
| 合計ジャッジ時間 | 23,578 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
39,936 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 167 ms
12,672 KB |
| testcase_04 | AC | 213 ms
15,596 KB |
| testcase_05 | AC | 227 ms
15,488 KB |
| testcase_06 | AC | 1 ms
5,376 KB |
| testcase_07 | AC | 859 ms
15,500 KB |
| testcase_08 | AC | 1,872 ms
23,676 KB |
| testcase_09 | AC | 1,892 ms
22,212 KB |
| testcase_10 | AC | 2 ms
5,376 KB |
| testcase_11 | AC | 1,034 ms
21,032 KB |
| testcase_12 | AC | 1,373 ms
24,700 KB |
| testcase_13 | AC | 1,294 ms
24,752 KB |
| testcase_14 | AC | 2 ms
5,376 KB |
| testcase_15 | AC | 762 ms
15,092 KB |
| testcase_16 | AC | 1,893 ms
24,772 KB |
| testcase_17 | AC | 1,491 ms
24,868 KB |
| testcase_18 | AC | 2 ms
5,376 KB |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| 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 | -- | - |
ソースコード
#include <cstdio>
#include <tuple>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
using Graph = vector< vector< pair<int, int> > >;
int main() {
int N, K; scanf("%d%d", &N, &K);
Graph G(N);
for(int i=0; i+1<N; i++) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
u--; v--; c--;
G[u].emplace_back(v, c);
G[v].emplace_back(u, c);
}
long long int ans = 0, ans_dbl = 0;
auto dfs = [&](auto&&f, int cur, int par) -> vector< pair<int, int> > {
vector< vector< pair<int, int> > > children;
vector< pair<int, int> > rec;
for(auto e : G[cur]) {
int to, color; tie(to, color) = e;
if(to == par) continue;
auto vec = f(f, to, cur);
children.emplace_back();
for(auto edge : vec) {
if(edge.first == color or edge.second == color) {
children.back().emplace_back(edge);
rec.emplace_back(edge);
if(edge.first != -1 and edge.second != -1) {
ans++;
}
}
else if(edge.first == -1) {
edge.first = color;
if(edge.first > edge.second) swap(edge.first, edge.second);
children.back().emplace_back(edge);
rec.emplace_back(edge);
if(edge.first != -1 and edge.second != -1) {
ans++;
}
}
}
// cur と to の間のパス
{
pair<int, int> short_edge(-1, color);
children.back().emplace_back(short_edge);
rec.emplace_back(short_edge);
}
sort(children.back().begin(), children.back().end());
}
sort(rec.begin(), rec.end());
for(const auto &v : children) {
for(const auto &e : v) {
if(e.first != -1 and e.second != -1) {
// 完全に一致するもの (2 回数えられる)
{
auto ub = upper_bound(rec.begin(), rec.end(), e);
auto lb = lower_bound(rec.begin(), rec.end(), e);
ans_dbl += ub - lb;
}
{
auto ub = upper_bound(v.begin(), v.end(), e);
auto lb = lower_bound(v.begin(), v.end(), e);
ans_dbl -= ub - lb;
}
// first だけ
{
pair<int, int> one(-1, e.first);
{
auto ub = upper_bound(rec.begin(), rec.end(), one);
auto lb = lower_bound(rec.begin(), rec.end(), one);
ans += ub - lb;
}
{
auto ub = upper_bound(v.begin(), v.end(), one);
auto lb = lower_bound(v.begin(), v.end(), one);
ans -= ub - lb;
}
}
// second だけ
{
pair<int, int> one(-1, e.second);
{
auto ub = upper_bound(rec.begin(), rec.end(), one);
auto lb = lower_bound(rec.begin(), rec.end(), one);
ans += ub - lb;
}
{
auto ub = upper_bound(v.begin(), v.end(), one);
auto lb = lower_bound(v.begin(), v.end(), one);
ans -= ub - lb;
}
}
}
else {
// 一色だけなら、他の一色だけのものと合わせられるかも
int c = e.second;
{
pair<int, int> p1(-1, 1 << 28);
pair<int, int> p2(-1, -1);
auto ub = upper_bound(rec.begin(), rec.end(), p1);
auto lb = lower_bound(rec.begin(), rec.end(), p2);
ans_dbl += ub - lb;
}
{
pair<int, int> p1(-1, 1 << 28);
pair<int, int> p2(-1, -1);
auto ub = upper_bound(v.begin(), v.end(), p1);
auto lb = lower_bound(v.begin(), v.end(), p2);
ans_dbl -= ub - lb;
}
{
pair<int, int> p(-1, c);
auto ub = upper_bound(rec.begin(), rec.end(), p);
auto lb = lower_bound(rec.begin(), rec.end(), p);
ans_dbl -= ub - lb;
}
{
pair<int, int> p(-1, c);
auto ub = upper_bound(v.begin(), v.end(), p);
auto lb = lower_bound(v.begin(), v.end(), p);
ans_dbl += ub - lb;
}
}
}
}
return rec;
};
dfs(dfs, 0, -1);
printf("%lld\n", ans + ans_dbl / 2);
return 0;
}