結果

問題 No.399 動的な領主
ユーザー ghassheeghasshee
提出日時 2016-07-22 11:46:45
言語 C90
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,939 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 22,912 KB
実行使用メモリ 806,144 KB
最終ジャッジ日時 2024-11-06 08:04:56
合計ジャッジ時間 17,368 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 10 ms
11,448 KB
testcase_05 AC 110 ms
84,096 KB
testcase_06 TLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 AC 9 ms
8,704 KB
testcase_11 AC 95 ms
81,536 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:18:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   18 | void push_N_N(u,v){
      |      ^~~~~~~~
main.c:18:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘order_nodes’:
main.c:31:6: warning: type of ‘r’ defaults to ‘int’ [-Wimplicit-int]
   31 | void order_nodes(r,parent){
      |      ^~~~~~~~~~~
main.c:31:6: warning: type of ‘parent’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘lca’:
main.c:49:5: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   49 | int lca(u,v){
      |     ^~~
main.c:49:5: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘check_nodes’:
main.c:58:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   58 | void check_nodes(u,v,lca_node){
      |      ^~~~~~~~~~~
main.c:58:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c:58:6: warning: type of ‘lca_node’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘main’:
main.c:77:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |     scanf("%d",&N_nodes);
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:79:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~
main.c:84:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   84 |     scanf("%d", &N_merchants);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~
main.c:86:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |         scanf("%d%d",&a[i],&b[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

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

#define DEPTH WIDTH*2-1
#define WIDTH 1024
#define SIZE WIDTH*128
#define PARENT WIDTH-1
#define ROOT 1
int N_nodes;
int N_merchants;
int N_N[SIZE][WIDTH*2];
long tax[SIZE];
int c=0;
long maxdepth,taxsum;
int a[SIZE],b[SIZE];
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;
}
int select_root(){
    int i,r,n,max=0;
    for (i=1;i<=N_nodes;i++)
        if ((n=N_N[i][0])>max){
            max = n;
            r = i;
        }
    return r;
}
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[v]++;
    tax[lca_node]--;
    tax[N_N[lca_node][PARENT]]--;
}

void lift_up_sum_imos(){
    int i,d,n;
    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",&a[i],&b[i]);
        lca_node = lca(a[i],b[i]);
        check_nodes(a[i],b[i],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