結果

問題 No.399 動的な領主
ユーザー ghassheeghasshee
提出日時 2016-07-22 11:29:00
言語 C90
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 2,045 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 23,296 KB
実行使用メモリ 808,996 KB
最終ジャッジ日時 2024-11-06 08:04:25
合計ジャッジ時間 4,426 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,640 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 11 ms
9,216 KB
testcase_05 AC 149 ms
80,896 KB
testcase_06 MLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
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:30:6: warning: type of ‘r’ defaults to ‘int’ [-Wimplicit-int]
   30 | void order_nodes(r,parent){
      |      ^~~~~~~~~~~
main.c:30:6: warning: type of ‘parent’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘lca’:
main.c:46:5: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   46 | int lca(u,v){
      |     ^~~
main.c:46:5: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘check_nodes’:
main.c:55:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   55 | void check_nodes(u,v,lca_node){
      |      ^~~~~~~~~~~
main.c:55:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c:55:6: warning: type of ‘lca_node’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘main’:
main.c:85:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |     scanf("%d",&N_nodes);
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:87:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~
main.c:92:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |     scanf("%d", &N_merchants);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~
main.c:94:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |         scanf("%d%d",&a[i],&b[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

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

#define DEPTH 1024*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];
int tax[SIZE];
int c=0;
long taxsum;
int a[SIZE],b[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++;
    N_N[r][DEPTH]=c;
    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]]--;
}

int depth(){
    int i,d,depth=0;
    for (i=1;i<=N_nodes;i++){
        if (depth<(d=N_N[i][DEPTH]))
            depth = d;
    }
    return depth;
}


void lift_up_sum_imos(){
    int i,d,n;
    for (d=depth();d>1;d--){
        for (i=1;i<=N_nodes;i++){
            if (N_N[i][DEPTH]!=d) continue;
            tax[N_N[i][PARENT]]+=tax[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