結果

問題 No.399 動的な領主
ユーザー ghassheeghasshee
提出日時 2016-07-20 21:55:17
言語 C90
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 2,022 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 24,448 KB
実行使用メモリ 819,420 KB
最終ジャッジ日時 2024-10-15 17:57:04
合計ジャッジ時間 4,807 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 3 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 14 ms
12,672 KB
testcase_05 AC 186 ms
117,576 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:21:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   21 | void push_N_N(u,v){
      |      ^~~~~~~~
main.c:21:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘order_nodes’:
main.c:34:6: warning: type of ‘root’ defaults to ‘int’ [-Wimplicit-int]
   34 | void order_nodes(root,parent){
      |      ^~~~~~~~~~~
main.c:34:6: warning: type of ‘parent’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘expand_to_root’:
main.c:43:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   43 | void expand_to_root(u,mer){
      |      ^~~~~~~~~~~~~~
main.c:43:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘expand_to_root2’:
main.c:52:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   52 | void expand_to_root2(u,mer){
      |      ^~~~~~~~~~~~~~~
main.c:52:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘remove_verbose_path’:
main.c:61:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
   61 | void remove_verbose_path(mer){
      |      ^~~~~~~~~~~~~~~~~~~
main.c: In function ‘paytax’:
main.c:65:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
   65 | void paytax(mer){
      |      ^~~~~~
main.c: In function ‘main’:
main.c:78:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |     scanf("%d",&number_of_nodes);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:80:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   80 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~
main.c:86:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |     scanf("%d", &number_of_merchant

ソースコード

diff # 

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

#define SIZE 100000

int number_of_nodes;
int number_of_merchants;
int path[SIZE][1000];
int path2[SIZE][1000];
int N_N[SIZE][1000];
int tax[SIZE];
int c,rootfound,root,taxsum;

void push_N_N();
int select_root();
void order_nodes();
void expand_to_root();
void remove_verbose_path();
void paytax();

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,max=0;
    for (i=1;i<=number_of_nodes;i++)
        if (N_N[i][0]>max){
            max = N_N[i][0];
            r = i;
        }
    return r;
}
void order_nodes(root,parent){
    int i;
    for (i=1;i<=N_N[root][0];i++)
    {
        if (N_N[root][i] == parent) N_N[root][i]*=(-1);
        else order_nodes(N_N[root][i],root);
    }
}

void expand_to_root(u,mer){
    path[mer][++path[mer][0]]=u;
    if (u==root) return;
    int i,ret;
    for (i=1;i<=N_N[u][0];i++){
        ret = -(N_N[u][i]);
        if (ret > 0) expand_to_root(ret,mer);
    }
}
void expand_to_root2(u,mer){
    path2[mer][++path2[mer][0]]=u;
    if (u==root) return;
    int i,ret;
    for (i=1;i<=N_N[u][0];i++){
        ret = -(N_N[u][i]);
        if (ret > 0) expand_to_root2(ret,mer);
    }
}
void remove_verbose_path(mer){
    while(path[mer][--path[mer][0]]==path2[mer][--path2[mer][0]]);
    ++path[mer][0];
}
void paytax(mer){
    int j;
    for (j=1;j<=path[mer][0];j++){
        taxsum+=(++tax[path[mer][j]]);
    }
    for (j=1;j<=path2[mer][0];j++){
        taxsum+=(++tax[path2[mer][j]]);
    }
}


int main(){
    int i,j,k, u,v,mer;
    scanf("%d",&number_of_nodes);
    for (i=1;i<number_of_nodes;i++){
        scanf("%d %d",&u,&v);
        push_N_N(u,v);
    }
    root = select_root();
    order_nodes(root,-1);

    scanf("%d", &number_of_merchants);
    for (mer=1;mer<=number_of_merchants;mer++){
        scanf("%d %d",&u,&v);
        expand_to_root(u,mer);
        expand_to_root2(v,mer);
        remove_verbose_path(mer);
        paytax(mer);
    }
    printf("%d\n",taxsum);
}
0