結果

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

ソースコード

diff #
raw source code 

/*
 * this is slow by #node times
 *
 * because
 * this program do not decide root.
 * every nodes are equal.
 *
 */

#include <stdlib.h>
#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 number_of_leaf_edge;
int a[SIZE], b[SIZE], tax[SIZE];
int e=0,count=0,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(u,v,edge){
    NxN_E[u][v]=edge;
    NxN_E[v][u]=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 NxN_E[n1][n2];
    }
    if (n1 == n2) {
        return -1;
    }
    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 if (N_N[node][0]>1) return 0;
    else {printf("N_N map error : node %d is invalid",node);return (-1);}
}

void push(int u, int v){
    int l,L,m,R,r, P,E, length_u,length_v,length_v2, i,j;

    // write parent( leaf edge )
    P = write_maps(u,v,0,0);
    write_N_N(u,v);
    length_u = N_E[u][0];
    length_v = N_E[v][0];

    // write composition of edge
    m = u;
    R = P;
    r = v;
    // now N_E[u][length_u] is P
    for (i=1; i<length_u; i++){
        L = N_E[m][i];
        l = otherNode(L,m);
        E = write_maps(l,r,L,R);
    }
    m = v;
    length_v2 = N_E[v][0];
    for (i = length_v; i<=length_v2;i++){
        R = N_E[m][i];
        r = otherNode(R,m);
        for (j = 1; j<=length_v; j++){
            L = N_E[m][j];
            l = otherNode(L,m);
            E = write_maps(l,r,L,R);
        }
    }
}




int main(int argc, char** argv)
{
    int i,j,u,v,q;
    scanf("%d", &number_of_leaf_edge);
    for (i=1; i <= number_of_leaf_edge-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;
    count = 0;
    int path = NxN_E[u][v];
    if (path==0) {
        printf("error : Mapping has no edge %4d\n ",path);
        exit(1);
    }
    // expand path to leaf edge
    expand_edge(u,path);
    stay[count++]=v;
    stay[count]=-1;

    // paytax at each village
    for (i=0;stay[i]>0;i++){
        paytax(stay[i]);
    }

}



void expand_edge(leftNode,edge){
    int e0,e1,e2,e3, leaf=0,l,L,m,R,r;
    e0=E_ExE[edge][0];e1=E_ExE[edge][1];
    e2=E_ExE[edge][2];e3=E_ExE[edge][3];

    if (e2==0 && e3==0) leaf=1;
    if (leaf) {
        stay[count++]=leftNode;
        return;
    }
    l = leftNode;
    r = otherNode(edge,l);


    if      ( l == E_ExE[e2][0] || l == E_ExE[e2][1] ) L = e2;
    else if ( l == E_ExE[e3][0] || l == E_ExE[e3][1] ) L = e3;
    else    printf("expand_error : cannot find Left Edge\n");

    m = otherNode(L,l);
    R = NxN_E[m][r];

    expand_edge(l,L);
    expand_edge(m,R);
}
0