結果

問題 No.399 動的な領主
ユーザー ghassheeghasshee
提出日時 2016-07-22 12:07:22
言語 C90
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 1,683 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 22,528 KB
実行使用メモリ 786,944 KB
最終ジャッジ日時 2024-11-06 08:05:56
合計ジャッジ時間 16,863 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 0 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 10 ms
9,216 KB
testcase_05 AC 106 ms
80,256 KB
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 AC 9 ms
8,576 KB
testcase_11 AC 91 ms
79,488 KB
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 TLE -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘push_N_N’:
main.c:17:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   17 | void push_N_N(u,v){
      |      ^~~~~~~~
main.c:17:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘order_nodes’:
main.c:21:6: warning: type of ‘r’ defaults to ‘int’ [-Wimplicit-int]
   21 | void order_nodes(r,parent){
      |      ^~~~~~~~~~~
main.c:21:6: warning: type of ‘parent’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘lca’:
main.c:37:5: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   37 | int lca(u,v){
      |     ^~~
main.c:37:5: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘check_nodes’:
main.c:46:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   46 | void check_nodes(u,v,lca_node){
      |      ^~~~~~~~~~~
main.c:46:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c:46:6: warning: type of ‘lca_node’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘main’:
main.c:60:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |     scanf("%d",&N_nodes);
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:62:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~
main.c:67:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |     scanf("%d", &N_merchants);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~
main.c:69:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>

#define WIDTH  1000
#define SIZE   WIDTH*101
#define PARENT WIDTH-1
#define ROOT   1

int N_nodes;
int N_merchants;
int N_N[SIZE][WIDTH*2];
int c;
long tax[SIZE];
long maxdepth,taxsum;
int dep[WIDTH][SIZE];

void push_N_N(u,v){
    N_N[u][++N_N[u][0]]=v;
    N_N[v][++N_N[v][0]]=u;
}
void order_nodes(r,parent){
    int i,j,child;
    c++;
    if(maxdepth<c) maxdepth=c;
    dep[c][++dep[c][0]]=r;
    N_N[r][PARENT]=parent;
    for (i=1;i<=N_N[r][0];i++){
        child = N_N[r][i];
        if (child == parent ) continue;
        N_N[child][PARENT+(c+1)]=i;
        for (j=1;j<c+1;j++)
            N_N[child][PARENT+j]=N_N[r][PARENT+j];
        order_nodes(child,r);
    }
    c--;
}
int lca(u,v){
    int i=1,uu=u,vv=v;
    while(N_N[u][PARENT+i]==N_N[v][PARENT+i]) i++;
    while(N_N[u][PARENT+i]!=0){
        uu=N_N[uu][PARENT];
        i++;
    }
    return uu;
}
void check_nodes(u,v,lca_node){
    tax[u]++;tax[lca_node]--;
    tax[v]++;tax[N_N[lca_node][PARENT]]--;
}
void lift_up_sum_imos(){
    int i,d;
    for (d=maxdepth;d>1;d--)
        for (i=1;i<=dep[d][0];i++)
            tax[N_N[dep[d][i]][PARENT]]+=tax[dep[d][i]];
}


int main(){
    int i,j,k, u,v,mer,lca_node;
    scanf("%d",&N_nodes);
    for (i=1;i<N_nodes;i++){
        scanf("%d %d",&u,&v);
        push_N_N(u,v);
    }
    N_N[ROOT][PARENT+1]=1;
    order_nodes(ROOT,SIZE-1);
    scanf("%d", &N_merchants);
    for (i=1;i<=N_merchants;i++){
        scanf("%d %d",&u,&v);
        lca_node = lca(u,v);
        check_nodes(u,v,lca_node);
    }
    lift_up_sum_imos();
    for (i=1;i<=N_nodes;i++)
        taxsum += (tax[i]*(tax[i]+1))/2;
    printf("%ld\n",taxsum);
}
0