#1168439 (C) No.3552 Triangular Coloring

• 問題: No.3552 Triangular Coloring
• ユーザー: 室澤栄登
• 提出日時: 2026-06-06 02:28:59
• 言語: C (gcc 15.2.0)
• 結果: WA
• 実行時間: -
• コード長: 5,132 bytes
• コンパイル時間: 365 ms
• コンパイル使用メモリ: 42,112 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2026-06-06 02:29:21
• 合計ジャッジ時間: 6,529 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	WA * 1
other	TLE * 1 -- * 16

ソースコード

#include<stdio.h>


typedef struct stack{
    int triangle0[40000];
    int triangle1[40000];
    int triangle2[40000];
    int tail;
}STACK;

    
void startSTACK(STACK *stacks, int rinsetsu_rist[], int counted[]){
    stacks->tail = 0;
    stacks->triangle0[0] = 0;
    stacks->triangle1[0] = rinsetsu_rist[0];
    stacks->triangle2[0] = rinsetsu_rist[1];
    counted[0] = 1;
    counted[rinsetsu_rist[0]] = 1;
    counted[rinsetsu_rist[1]] = 1;
}
void pushSTACK(STACK *stackp, int i0, int i1, int i2){
    stackp->tail++;
    int tail = stackp->tail;
    stackp->triangle0[tail] = i0;
    stackp->triangle1[tail] = i1;
    stackp->triangle2[tail] = i2;
}
void popSTACK(STACK *stackp, int triangle[]){
    int tail = stackp->tail;
    triangle[0] = stackp->triangle0[tail];
    triangle[1] = stackp->triangle1[tail];
    triangle[2] = stackp->triangle2[tail];
    stackp->tail--;
}
int find_nextdot(int N, int M, int counted[], int rinsetsu_rist[], int rinsetsu_pos[], int i0, int i1, int i2){
    int i, j;
    int count;
    for(i = 0; i < N - 1; i++){
        count = 0;
        if(counted[i] == 0){
            for(j = rinsetsu_pos[i]; j < rinsetsu_pos[i + 1]; j++){
                if(rinsetsu_rist[j] == i0 || rinsetsu_rist[j] == i1 || rinsetsu_rist[j] == i2){
                    count++;
                }
            }
        }
        if(count == 3){
            counted[i] = 1;
            return i;
        }
    }
    count = 0;
    if(counted[N - 1] == 0){
        for(j = rinsetsu_pos[N - 1]; j < 2 * M; j++){
            if(rinsetsu_rist[j] == i0 || rinsetsu_rist[j] == i1 || rinsetsu_rist[j] == i2){
                count++;
            }
        }
    }
    if(count == 3){
        counted[N - 1] = 1;
        return N - 1;
    }
    return -1;
}
void jikkou0(STACK *stack, int rinsetsu_rist[], int result[], int counted[]){
    startSTACK(stack, rinsetsu_rist, counted);
    result[0] = 1;
    result[rinsetsu_rist[0]] = 2;
    result[rinsetsu_rist[1]] = 3;
}
void jikkou1(int N, int M, int counted[], int rinsetsu_rist[], int rinsetsu_pos[], STACK *stack, int result[]){
        int triangle[3];
        int i, j;
        popSTACK(stack, triangle);
        i = find_nextdot(N, M, counted, rinsetsu_rist, rinsetsu_pos, triangle[0], triangle[1], triangle[2]);
        j = find_nextdot(N, M, counted, rinsetsu_rist, rinsetsu_pos, triangle[0], triangle[1], triangle[2]);
        if(i >= 0 && j == -1){
            result[i] = 10 - result[triangle[0]] - result[triangle[1]] - result[triangle[2]];
            pushSTACK(stack, triangle[0], triangle[1], i);
            pushSTACK(stack, triangle[1], triangle[2], i);
            pushSTACK(stack, triangle[2], triangle[0], i);
        }else if(i >= 0 && j >= 0){
            result[i] = 10 - result[triangle[0]] - result[triangle[1]] - result[triangle[2]];
            result[j] = 10 - result[triangle[0]] - result[triangle[1]] - result[triangle[2]];
            pushSTACK(stack, triangle[0], triangle[1], i);
            pushSTACK(stack, triangle[1], triangle[2], i);
            pushSTACK(stack, triangle[2], triangle[0], i);
            pushSTACK(stack, triangle[0], triangle[1], j);
            pushSTACK(stack, triangle[1], triangle[2], j);
            pushSTACK(stack, triangle[2], triangle[0], j);
        }
}

void jikkou(int N, int M, int counted[], int rinsetsu_rist[], int rinsetsu_pos[], STACK *stack, int result[]){
    int triangle[3];
    popSTACK(stack, triangle);
    int i, j;
    i = find_nextdot(N, M, counted, rinsetsu_rist, rinsetsu_pos, triangle[0], triangle[1], triangle[2]);
    if(i >= 0){
        result[i] = 10 - result[triangle[0]] - result[triangle[1]] - result[triangle[2]];
        pushSTACK(stack, triangle[0], triangle[1], i);
        pushSTACK(stack, triangle[1], triangle[2], i);
        pushSTACK(stack, triangle[2], triangle[0], i);
    }
}

int main(void){
    int i, j;
    int N, M;
    scanf("%d%d", &N, &M);
    int result[N];
    int rinsetsu_rist[2 * M];
    int rinsetsu_pos[N];
    int rinsetsu_index[N];

    int u[M], v[M];

    for(i = 0; i < M; i++){
        scanf("%d%d", &u[i], &v[i]);
        u[i]--;
        v[i]--;
    }

    for(i = 0; i < N; i++){
        rinsetsu_pos[i] = 0;
        rinsetsu_index[i] = 0;
    }

    for(i = 0; i < M; i++){
        for(j = u[i] + 1; j < N; j++){
            rinsetsu_pos[j]++;
        }
        for(j = v[i] + 1; j < N; j++){
            rinsetsu_pos[j]++;
        }
    }

    for(i = 0; i < M; i++){
        rinsetsu_rist[rinsetsu_pos[u[i]] + rinsetsu_index[u[i]]] = v[i];
        rinsetsu_index[u[i]]++;

        rinsetsu_rist[rinsetsu_pos[v[i]] + rinsetsu_index[v[i]]] = u[i];
        rinsetsu_index[v[i]]++;
    }

    STACK stackT;



    int counted[N];
    for(i = 0; i < N; i++){
        counted[i] = 0;
    }

    jikkou0(&stackT, rinsetsu_rist, result, counted);
    jikkou1(N, M, counted, rinsetsu_rist, rinsetsu_pos, &stackT, result);
    while(stackT.tail >= 0){
        jikkou(N, M, counted, rinsetsu_rist, rinsetsu_pos, &stackT, result);
    }


    printf("%s\n", "yes");
    for(i = 0; i < N; i++){
        printf("%d ", result[i]);
    }

    return 0;
}