結果

問題 No.399 動的な領主
ユーザー ghassheeghasshee
提出日時 2016-07-20 21:29:56
言語 C90
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,837 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 23,680 KB
実行使用メモリ 126,976 KB
最終ジャッジ日時 2024-10-15 17:56:34
合計ジャッジ時間 7,524 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 15 ms
13,056 KB
testcase_05 AC 201 ms
126,976 KB
testcase_06 TLE -
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:22:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   22 | void push_N_N(u,v){
      |      ^~~~~~~~
main.c:22:6: warning: type of ‘v’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘order_nodes’:
main.c:35:6: warning: type of ‘root’ defaults to ‘int’ [-Wimplicit-int]
   35 | void order_nodes(root,parent){
      |      ^~~~~~~~~~~
main.c:35:6: warning: type of ‘parent’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘expand_to_root’:
main.c:44:6: warning: type of ‘u’ defaults to ‘int’ [-Wimplicit-int]
   44 | void expand_to_root(u,mer){
      |      ^~~~~~~~~~~~~~
main.c:44:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘remove_verbose_path’:
main.c:53:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
   53 | void remove_verbose_path(mer){
      |      ^~~~~~~~~~~~~~~~~~~
main.c: In function ‘paytax’:
main.c:57:6: warning: type of ‘mer’ defaults to ‘int’ [-Wimplicit-int]
   57 | void paytax(mer){
      |      ^~~~~~
main.c: In function ‘main’:
main.c:70:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |     scanf("%d",&number_of_nodes);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:72:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~
main.c:77:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |     scanf("%d", &number_of_merchants);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:79:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |         scanf("%d %d",&u,&v);
      |         ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

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

#define SIZE 10000
#define WIDTH 1024*16


int number_of_nodes;
int number_of_merchants;
int path[SIZE*4][SIZE];
int N_N[SIZE][SIZE];
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 remove_verbose_path(mer){
    while(path[mer][--path[mer][0]]==path[mer+WIDTH][--path[mer+WIDTH][0]]);
    ++path[mer][0];
}
void paytax(mer){
    int j;
    for (int j=1;j<=path[mer][0];j++){
        taxsum+=(++tax[path[mer][j]]);
    }
    for (int j=1;j<=path[mer+WIDTH][0];j++){
        taxsum+=(++tax[path[mer+WIDTH][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_root(v,mer+WIDTH);
        remove_verbose_path(mer);
        paytax(mer);
    }
    printf("%d\n",taxsum);
}
0