제출 #237736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237736		Charis02	항공 노선도 (JOI18_airline)	C++14	100 / 100	998 ms	23352 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <iostream>

bool ison(int i,int j)
{
    return (i>>j)&1;
}

using namespace std;

void Alice( int N, int M, int A[], int B[] ){
    int cnt = M;

	for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < 10;j++)
        {
            if(ison(i,j))
            {
                cnt++;
            }
        }
    }

    for(int i = 0;i < 9;i++)
        cnt++;

    for(int i = 0;i < N;i++)
        cnt++;

    cnt++;

	InitG( N+12,cnt);

	cnt = M;

	for(int i = 0;i < M;i++)
    {
        MakeG(i,A[i],B[i]);
    }

	for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < 10;j++)
        {
            if(ison(i,j))
            {
                MakeG(cnt,i,N+j);
                cnt++;
            }
        }
    }

    for(int i = 0;i < 9;i++)
    {
        MakeG(cnt,N+i,N+i+1);
        cnt++;
    }

    for(int i = 0;i < N;i++)
    {
        MakeG(cnt,i,N+10);
        cnt++;
    }

    MakeG(cnt,N+10,N+11);
    cnt++;

    return;
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#define MAXN 1034

using namespace std;

int deg[MAXN];
int neighbor[MAXN];
bool regular[MAXN];
int real_number[MAXN];
bool graph[MAXN][MAXN];
bool vis[MAXN];

void Bob( int V, int U, int C[], int D[] ){
    int N =V-12;

    for(int i = 0;i< U;i++)
    {
        deg[C[i]]++;
        neighbor[C[i]]= D[i];
        deg[D[i]]++;
        neighbor[D[i]] = C[i];

        graph[C[i]][D[i]] = 1;
        graph[D[i]][C[i]] = 1;
    }

    int root = 0;
    int dummy = 0;

    for(int i = 0;i < V;i++)
    {
       // cout << "here " << i << " " << deg[i] << endl;
        if(deg[i] == 1)
        {
            if(deg[neighbor[i]] == N+1)
            {
                dummy = i;
                root = neighbor[i];
            }
        }
    }

   // cout << "here " << root << " " << dummy << "  " << deg[root] << " " << deg[dummy] << endl;

    for(int i = 0;i < U;i++)
    {
        if(C[i] != root && D[i] != root)
            continue;

        if(C[i] == root)
            regular[D[i]] = true;
        else
            regular[C[i]] = true;
    }

    int nxt = 0;
    int mini = N;

    for(int i = 0;i < V;i++)
    {
        if(regular[i] || i == root || i == dummy)
            continue;

        if(deg[i] < mini)
        {
            nxt=i;
            mini=deg[i];
        }
    }

    for(int i = 9;i >= 0;i--)
    {
        int cur = nxt;
        vis[cur]=true;
        for(int j = 0;j < V;j++)
        {
            if(j == root || j == dummy)
                continue;
            if(!regular[j] && !vis[j] && graph[cur][j])
            {
                nxt = j;
                continue;
            }
            if(graph[cur][j])
                real_number[j] += (1 << i);
        }
    }

   /* for(int i = 0;i < V;i++)
    {
        cout << i << " is ";
        if(i == root)
            cout << " the root\n";
        else if(i == dummy)
            cout << " the dummy\n";
        else if(regular[i])
            cout << " regular with number " << real_number[i] << "\n";
        else
            cout << " irregular\n";
    }*/

    int M =0;

   // cout << endl << endl;

    for(int i = 0;i < V;i++)
    {
        if(!regular[i])
            continue;
        for(int j = 0;j < i;j++)
        {
            if(!regular[j])
                continue;
            if(!graph[i][j])
                continue;
          //  cout << "new edge " << i << " " << j << endl;
            M++;
        }
    }

    InitMap(N,M);

    for(int i = 0;i < V;i++)
    {
        if(!regular[i])
            continue;
        for(int j = 0;j < i;j++)
        {
            if(!regular[j])
                continue;
            if(!graph[i][j])
                continue;
            MakeMap(real_number[i],real_number[j]);
        }
    }

    return;
}

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63