oj.uz

Submission #659

# Submission time Handle Problem Language Result Execution time Memory
659 2013-03-01T01:28:16 Z pl0892029 지도 색칠하기 (GA3_map) C++
0 / 120
 0 ms 920 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Incorrect 0 ms 920 KB Output isn't correct
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 0 ms 920 KB Output is correct
6 Correct 0 ms 920 KB Output is correct
7 Incorrect 0 ms 920 KB Output isn't correct
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 0 ms 920 KB Output is correct
6 Incorrect 0 ms 920 KB Output isn't correct
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 0 ms 920 KB Output is correct
6 Incorrect 0 ms 920 KB Output isn't correct
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 0 ms 920 KB Output is correct
6 Incorrect 0 ms 920 KB Output isn't correct
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -
14 Halted 0 ms 0 KB -
15 Halted 0 ms 0 KB -
16 Halted 0 ms 0 KB -
17 Halted 0 ms 0 KB -
18 Halted 0 ms 0 KB -
19 Halted 0 ms 0 KB -
20 Halted 0 ms 0 KB -
21 Halted 0 ms 0 KB -
22 Halted 0 ms 0 KB -
23 Halted 0 ms 0 KB -
24 Halted 0 ms 0 KB -
25 Halted 0 ms 0 KB -
26 Halted 0 ms 0 KB -
27 Halted 0 ms 0 KB -
28 Halted 0 ms 0 KB -
29 Halted 0 ms 0 KB -
30 Halted 0 ms 0 KB -