結果

問題 No.399 動的な領主
ユーザー ghassheeghasshee
提出日時 2016-07-19 06:20:47
言語 C90
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,652 bytes
コンパイル時間 645 ms
コンパイル使用メモリ 22,400 KB
実行使用メモリ 575,228 KB
最終ジャッジ日時 2024-04-23 16:45:16
合計ジャッジ時間 6,436 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,760 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 WA -
testcase_11 MLE -
testcase_12 RE -
testcase_13 RE -
testcase_14 MLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘add_E_ExE’:
main.c:23:5: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   23 | int add_E_ExE(n1,n2,e1,e2){
      |     ^~~~~~~~~
main.c:23:5: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:23:5: warning: type of ‘e1’ defaults to ‘int’ [-Wimplicit-int]
main.c:23:5: warning: type of ‘e2’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘add_N_E’:
main.c:30:6: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   30 | void add_N_E(n1,n2,edge){
      |      ^~~~~~~
main.c:30:6: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:30:6: warning: type of ‘edge’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘add_NxN_E’:
main.c:34:6: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   34 | void add_NxN_E(n1,n2,edge){
      |      ^~~~~~~~~
main.c:34:6: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:34:6: warning: type of ‘edge’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘add_N_N’:
main.c:38:6: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   38 | void add_N_N(n1,n2){
      |      ^~~~~~~
main.c:38:6: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘add_maps’:
main.c:43:5: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   43 | int add_maps(n1,n2,e1,e2){
      |     ^~~~~~~~
main.c:43:5: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:43:5: warning: type of ‘e1’ defaults to ‘int’ [-Wimplicit-int]
main.c:43:5: warning: type of ‘e2’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘otherNode’:
main.c:51:5: warning: type of ‘edge’ defaults to ‘int’ [-Wimplicit-int]
   51 | int otherNode(edge,node){
      |     ^~~~~~~~~
main.c:51:5: warning: type of ‘node’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘isLeaf’:
mai

ソースコード

diff # 

#include "stdio.h"
#define SIZE 10000

int NxN_E[SIZE][SIZE];
int N_N[SIZE][SIZE];
int N_E[SIZE][SIZE];
int E_ExE[SIZE*5000][4];
int a[SIZE], b[SIZE], tax[SIZE];
int e;
int c;
int taxsum = 0;
int COMPLETE = 0;
int stay[SIZE];



void expand_edge();
int find_edge();
void paytax();
void move_and_paytax();

int add_E_ExE(n1,n2,e1,e2){
    E_ExE[++e][0]=n1;
    E_ExE[e][1]=n2;
    E_ExE[e][2]=e1;
    E_ExE[e][3]=e2;
    return e;
}
void add_N_E(n1,n2,edge){
    N_E[n1][++N_E[n1][0]]=edge;
    N_E[n2][++N_E[n2][0]]=edge;
}
void add_NxN_E(n1,n2,edge){
    NxN_E[n1][n2]=edge;
    NxN_E[n2][n1]=edge;
}
void add_N_N(n1,n2){
    N_N[n1][++N_N[n1][0]]=n2;
    N_N[n2][++N_N[n2][0]]=n1;
}

int add_maps(n1,n2,e1,e2){
    if (NxN_E[n1][n2]) return 0;
    if (n1 == n2) return 0;
    int edge = add_E_ExE(n1,n2,e1,e2);
    add_N_E(n1,n2,edge);
    add_NxN_E(n1,n2,edge);
    return edge;
}
int otherNode(edge,node){
    if (node==E_ExE[edge][0])
        return E_ExE[edge][1];
    else
        return E_ExE[edge][0];
}
int isLeaf(node){
    if (N_N[node][0]==1) return 1;
    else return 0;
}

void push(int u, int v){
    int i,j,m;
    int P = add_maps(u,v,0,0);
    add_N_N(u,v);
    if (!isLeaf(u)){
        for (i=1;i<=N_E[u][0];i++){
            add_maps(otherNode(N_E[u][i],u),v,N_E[u][i],P);
            if (!isLeaf(v)){
                m=N_E[v][0];
                for (j=1;j<=m;j++)
                    add_maps(otherNode(N_E[u][i],u),otherNode(N_E[v][j],v),N_E[u][i],N_E[v][j]);
            }
        }
    }
}


int main(int argc, char** argv)
{
    int i,j,n,u,v,q;
    scanf("%d", &n);
    for (i=1; i <= n-1; i++)
    {
        scanf("%d%d", &u, &v);
        push(u,v);
    }
    scanf("%d", &q);
    for (i=1; i<=q; i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        move_and_paytax(a[i],b[i]);
    }
    printf("%d\n",taxsum);
}


void paytax(village) {
    taxsum += (++tax[(village)]);
}


void move_and_paytax(u,v)
{
    int i;
    c = 0;
    int E=NxN_E[u][v];
    expand_edge(u,v,E);
    stay[c++]=v;
    stay[c]=-1;
    paytax(stay[0]);
    for (i=1;stay[i]>0;i++){
        paytax(stay[i]);
    }
}

void expand_edge(u,v,E){
    int L,R,l,r,mid;
    if (u == E_ExE[E][0]){
        l = u;r = v;
        L=E_ExE[E][2];R=E_ExE[E][3];
    } else {
        l = v; r = u;
        L=E_ExE[E][3];R=E_ExE[E][2];
    }
    mid=otherNode(L,l);
    if (R==0) {
        //leaf_edge
        if (l == u) stay[c++]=l;
        else stay[c++]=r;
    }else{
        if (u==l){
            expand_edge(l,mid,L);
            expand_edge(mid,r,R);
        }else{
            expand_edge(r,mid,R);
            expand_edge(mid,l,L);
        }
    }
}
0