Submission #658

#	Time	Username	Problem	Language	Result	Execution time	Memory
658		pl0892029	지도 색칠하기 (GA3_map)	C++98	0 / 120	0 ms	920 KiB

map

#include <algorithm>
using namespace std;

typedef struct edge
{
    int u,v;
}edge;

bool cmp(edge a,edge b){return a.u==b.u ? a.v<b.v : a.u<b.u;}

edge arr[400];
int table[400], n;
int chk[21], cnt[21], queue[21], h,t;

long long NumberOfMaps(int N,int M,int *A,int *B)
{
    int i,j,m;
    long long ret = 1, tmp = 1;
    for(i=0;i<M;i++)
    {
        arr[2*i].u=A[i],arr[2*i].v=B[i];
        arr[2*i+1].u=B[i], arr[2*i+1].v=A[i];
    }
    n=2*M;
    sort(arr,arr+n,cmp);
    for(i=1;i<n;i++) if(arr[i-1].u==arr[i].u && arr[i-1].v==arr[i].v) table[i]=1;
    for(i=1;i<=N;i++)
    {
        if( chk[i]==2 ) continue;
        tmp = 1, h=0, t=0;
        queue[t++]=i, chk[i]=1;
        while(h<t)
        {
            m=queue[h++];
            chk[m]=2; // finish
            tmp *= 4-cnt[m];
            for(j=0;j<n;j++)
            {
                if(table[j]==1) continue;
                if(arr[j].u==m)
                {
                    if(chk[arr[j].v]<2) cnt[arr[j].v]++;
                    if(chk[arr[j].v]==0)
                    {
                        queue[t++]=arr[j].v;
                        chk[arr[j].v]=1;
                    }
                }
            }
        }
        ret *= tmp;
    }
    return ret;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35