結果

問題 No.1769 Don't Stop the Game
ユーザー 👑 ygussany
提出日時 2021-11-13 14:32:57
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 154 ms / 3,000 ms
コード長 2,915 bytes
コンパイル時間 546 ms
コンパイル使用メモリ 33,132 KB
実行使用メモリ 46,596 KB
最終ジャッジ日時 2024-06-29 18:04:52
合計ジャッジ時間 4,093 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
typedef struct Edge {
    struct Edge *next;
    int v, cost;
} edge;
#define HASH 1000003
const int H_Mod = HASH;
typedef struct List {
    struct List *next;
    int v, cur;
} list;
void DFS(edge* adj[], int u, int par[], int val[], list* hash[])
{
    int h = val[u] % H_Mod, w;
    edge *p;
    list *hp;
    for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == val[u]) break;
    par[u] = hp->cur;
    for (p = adj[u]; p != NULL; p = p->next) {
        w = p->v;
        hp->cur = w;
        if (par[w] < 0) DFS(adj, w, par, val, hash);
        hp->cur = par[u];
    }
}
int main()
{
    int i, N, u, w, c;
    edge *adj[200001] = {}, e[400001], *p;
    scanf("%d", &N);
    for (i = 0; i < N - 1; i++) {
        scanf("%d %d %d", &u, &w, &c);
        e[i*2].v = w;
        e[i*2+1].v = u;
        e[i*2].cost = c;
        e[i*2+1].cost = c;
        e[i*2].next = adj[u];
        e[i*2+1].next = adj[w];
        adj[u] = &(e[i*2]);
        adj[w] = &(e[i*2+1]);
    }
    
    int h, par[200001] = {}, val[200001], q[200001], head, tail;
    list *hash[HASH] = {}, hd[200001], *hp;
    par[1] = 1;
    val[1] = 0;
    q[0] = 1;
    for (head = 0, tail = 1; head < tail; head++) {
        u = q[head];
        h = val[u] % H_Mod;
        for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == val[u]) break;
        if (hp == NULL) {
            hd[u].v = val[u];
            hd[u].cur = 0;
            hd[u].next = hash[h];
            hash[h] = &(hd[u]);
        }
        
        for (p = adj[u]; p != NULL; p = p->next) {
            w = p->v;
            if (par[w] == 0) {
                par[w] = u;
                val[w] = val[u] ^ p->cost;
                q[tail++] = w;
            }
        }
    }
    
    int size[200001] = {};
    for (head--; head >= 0; head--) {
        u = q[head];
        size[u]++;
        if (head != 0) size[par[u]] += size[u];
    }
    for (u = 1; u <= N; u++) par[u] = -1;
    DFS(adj, 1, par, val, hash);
    
    int k;
    edge *aux[400001] = {}, f[400001];
    for (u = 1, i = 0, k = N; u <= N; u++) {
        if (par[u] == 0) {
            h = val[u] % H_Mod;
            for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == val[u]) break;
            if (hp->cur == 0) hp->cur = ++k;
            f[i].v = u;
            f[i].next = aux[hp->cur];
            aux[hp->cur] = &(f[i++]);
        } else {
            f[i].v = u;
            f[i].next = aux[par[u]];
            aux[par[u]] = &(f[i++]);
        }
    }
    
    for (u = 2; u <= N; u++) par[u] = 0;
    par[1] = 1;
    q[0] = 1;
    for (head = 0, tail = 1; head < tail; head++) {
        u = q[head];
        for (p = adj[u]; p != NULL; p = p->next) {
            w = p->v;
            if (par[w] == 0) {
                par[w] = u;
                q[tail++] = w;
            }
        }
    }
    
    int j;
    long long ans = 0, tmp;
    edge *pp;
    for (i = N + 1; i <= k; i++) {
        for (p = aux[i], j = 0, tmp = N, tail = 0; p != NULL; p = p->next, j++) {
            w = p->v;
            tmp -= size[w];
            q[tail++] = w;
        }
        ans += tmp * j;
        for (head = 0; head < tail; head++) {
            u = q[head];
            for (p = adj[u]; p != NULL; p = p->next) {
                w = p->v;
                if (w == par[u]) continue;
                for (pp = aux[w], j = 0, tmp = size[w]; pp != NULL; pp = pp->next, j++) {
                    tmp -= size[pp->v];
                    q[tail++] = pp->v;
                }
                ans += tmp * (j + 1);
            }
        }
    }
    printf("%lld\n", ans);
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0