#104872 (C90) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: ghasshee
• 提出日時: 2016-07-19 06:19:52
• 言語: C90 (gcc 12.4.0)
• 結果: CE (最新)
  WA
  (最初)
• 実行時間: -
• コード長: 2,652 bytes
• コンパイル時間: 102 ms
• コンパイル使用メモリ: 21,700 KB
• 最終ジャッジ日時: 2026-02-23 22:02:37
• ジャッジサーバーID （参考情報）: judge2 / judge2

コンパイルメッセージ

main.c: In function ‘expand_edge’:
main.c:128:9: error: C++ style comments are not allowed in ISO C90
  128 |         //leaf_edge
      |         ^
main.c:128:9: note: (this will be reported only once per input file)
main.c: In function ‘main’:
main.c:82:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
main.c:85:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |         scanf("%d%d", &u, &v);
      |         ^~~~~~~~~~~~~~~~~~~~~
main.c:88:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |     scanf("%d", &q);
      |     ^~~~~~~~~~~~~~~
main.c:91:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   91 |         scanf("%d%d",&a[i],&b[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

#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*1000][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);
        }
    }
}