#905476 (C) No.2427 Tree Distance Two

• 問題: No.2427 Tree Distance Two
• ユーザー: 👑 chro_96
• 提出日時: 2023-08-18 22:04:11
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 170 ms / 2,000 ms
• コード長: 1,459 bytes
• コンパイル時間: 787 ms
• コンパイル使用メモリ: 29,440 KB
• 実行使用メモリ: 46,336 KB
• 最終ジャッジ日時: 2024-05-06 04:07:23
• 合計ジャッジ時間: 5,743 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	13 ms; 18,176 KB
testcase_01	AC	13 ms; 18,304 KB
testcase_02	AC	12 ms; 18,304 KB
testcase_03	AC	170 ms; 18,304 KB
testcase_04	AC	11 ms; 18,176 KB
testcase_05	AC	167 ms; 18,304 KB
testcase_06	AC	11 ms; 18,304 KB
testcase_07	AC	127 ms; 18,176 KB
testcase_08	AC	144 ms; 18,304 KB
testcase_09	AC	128 ms; 18,304 KB
testcase_10	AC	141 ms; 18,304 KB
testcase_11	AC	133 ms; 18,304 KB
testcase_12	AC	138 ms; 18,304 KB
testcase_13	AC	150 ms; 18,304 KB
testcase_14	AC	125 ms; 46,336 KB
testcase_15	AC	11 ms; 18,304 KB
testcase_16	AC	12 ms; 18,304 KB
testcase_17	AC	11 ms; 18,304 KB
testcase_18	AC	12 ms; 18,304 KB
testcase_19	AC	13 ms; 18,304 KB
testcase_20	AC	15 ms; 18,304 KB
testcase_21	AC	16 ms; 18,176 KB
testcase_22	AC	14 ms; 18,304 KB
testcase_23	AC	13 ms; 18,304 KB
testcase_24	AC	14 ms; 18,176 KB
testcase_25	AC	43 ms; 18,304 KB
testcase_26	AC	101 ms; 18,304 KB
testcase_27	AC	70 ms; 18,304 KB
testcase_28	AC	152 ms; 18,304 KB
testcase_29	AC	136 ms; 18,304 KB
testcase_30	AC	97 ms; 18,304 KB
testcase_31	AC	62 ms; 18,304 KB
testcase_32	AC	98 ms; 18,304 KB
testcase_33	AC	82 ms; 18,304 KB
testcase_34	AC	30 ms; 18,304 KB

ソースコード

#include <stdio.h>

typedef struct list {
  int v;
  struct list *n;
} list;

void func1 (int v, list **e, int tmp_d, int *d, int *cnt, int *visited, int *ans) {
  list *l = e[v];
  
  d[v] = tmp_d;
  visited[v] = 1;
  while (l != NULL) {
    if (visited[l->v] <= 0) {
      func1(l->v, e, tmp_d+1, d, cnt, visited, ans);
      cnt[v]++;
      ans[v] += cnt[l->v];
    }
    l = l->n;
  }
  
  return;
}

void func2 (int v, list **e, int *cnt, int *visited, int *ans) {
  list *l = e[v];
  
  visited[v] = 2;
  while (l != NULL) {
    if (visited[l->v] <= 1) {
      func2(l->v, e, cnt, visited, ans);
      ans[l->v] += cnt[v]-1;
    }
    l = l->n;
  }
  
  return;
}

int main () {
 int n = 0;
 int u = 0;
 int v = 0;
 
 int res = 0;
 
 int ans[300000] = {};
 
 int d[300000] = {};
 int dcnt[300002] = {};
 
 list pool[599998] = {};
 int used = 0;
 
 list *e[300000] = {};
 
 int visited[300000] = {};
 int cnt[300000] = {};
 
 res = scanf("%d", &n);
 for (int i = 0; i < n-1; i++) {
   res = scanf("%d", &u);
   res = scanf("%d", &v);
   u--;
   v--;
   pool[used].v = v;
   pool[used].n = e[u];
   e[u] = pool+used;
   used++;
   pool[used].v = u;
   pool[used].n = e[v];
   e[v] = pool+used;
   used++;
 }
 
 func1(0, e, 0, d, cnt, visited, ans);
 func2(0, e, cnt, visited, ans);
 
 for (int i = 0; i < n; i++) {
   dcnt[d[i]]++;
 }
 
 for (int i = 0; i < n; i++) {
   if (d[i] > 1) {
     ans[i] += 1;
   }
   printf("%d\n", ans[i]);
 }
 
 return 0;
}