結果

問題 No.399 動的な領主
コンテスト
ユーザー ghasshee
提出日時 2016-07-19 15:31:17
言語 C90
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 2,836 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 22,912 KB
実行使用メモリ 763,072 KB
最終ジャッジ日時 2024-10-15 17:20:10
合計ジャッジ時間 4,112 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 3 MLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘write_E_ExE’:
main.c:21:5: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   21 | int write_E_ExE(n1,n2,e1,e2){
      |     ^~~~~~~~~~~
main.c:21:5: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:21:5: warning: type of ‘e1’ defaults to ‘int’ [-Wimplicit-int]
main.c:21:5: warning: type of ‘e2’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘write_N_E’:
main.c:28:6: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   28 | void write_N_E(n1,n2,edge){
      |      ^~~~~~~~~
main.c:28:6: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:28:6: warning: type of ‘edge’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘write_NxN_E’:
main.c:32:6: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   32 | void write_NxN_E(n1,n2,edge){
      |      ^~~~~~~~~~~
main.c:32:6: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:32:6: warning: type of ‘edge’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘write_N_N’:
main.c:36:6: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   36 | void write_N_N(n1,n2){
      |      ^~~~~~~~~
main.c:36:6: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘write_maps’:
main.c:41:5: warning: type of ‘n1’ defaults to ‘int’ [-Wimplicit-int]
   41 | int write_maps(n1,n2,e1,e2){
      |     ^~~~~~~~~~
main.c:41:5: warning: type of ‘n2’ defaults to ‘int’ [-Wimplicit-int]
main.c:41:5: warning: type of ‘e1’ defaults to ‘int’ [-Wimplicit-int]
main.c:41:5: warning: type of ‘e2’ defaults to ‘int’ [-Wimplicit-int]
main.c: In function ‘otherNode’:
main.c:49:5: warning: type of ‘edge’ defaults to ‘int’ [-Wimplicit-int]
   49 | int otherNode(edge,node){
      |     ^~~~~~~~~
main.c:49:5: warning: type of ‘node’ defaults to ‘int’ [-Wimplicit-int]
main.c:

ソースコード

diff #
raw source code 

#include "stdio.h"
#define SIZE 10000

// 4 MapTables
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,c,taxsum = 0;
int COMPLETE = 0;
int stay[SIZE];


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

int write_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 write_N_E(n1,n2,edge){
    N_E[n1][++N_E[n1][0]]=edge;
    N_E[n2][++N_E[n2][0]]=edge;
}
void write_NxN_E(n1,n2,edge){
    NxN_E[n1][n2]=edge;
    NxN_E[n2][n1]=edge;
}
void write_N_N(n1,n2){
    N_N[n1][++N_N[n1][0]]=n2;
    N_N[n2][++N_N[n2][0]]=n1;
}

int write_maps(n1,n2,e1,e2){
    if (NxN_E[n1][n2]) return 0;
    if (n1 == n2) return 0;
    int edge = write_E_ExE(n1,n2,e1,e2);
    write_N_E(n1,n2,edge);
    write_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,n,m,o;
    int P = write_maps(u,v,0,0);
    write_N_N(u,v);
    if (!isLeaf(u)){
        n = N_E[u][0];
        for (i=1;i<=n;i++){
            write_maps(otherNode(N_E[u][i],u),v,N_E[u][i],P);
        }
    }
    if (!isLeaf(v)){
        n = N_E[u][0];
        m = N_E[v][0];
        for (j=1;j<=m;j++){
            for (i=1;i<=n;i++){
                if (N_E[v][j] == N_E[u][i]) continue;
                if (i==1)o=u; else o=otherNode(N_E[u][i],u);
                write_maps(o,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