제출 #1363201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363201		solution6312	항공 노선도 (JOI18_airline)	C++17	0 / 100	112 ms	26300 KiB

Alice

#include "Alicelib.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
using pii=pair<int, int>;

void InitG(int V, int U);
void MakeG(int pos, int C, int D);

void Alice(int N, int M, int A[], int B[])
{
    vector<pii> e;
    for (int i=0; i<M; i++) e.push_back({A[i], B[i]});
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<10; j++)
        {
            if ((i>>j)&1)
            {
                e.push_back({i, N+j});
            }
        }
    }
    for (int i=0; i<10; i++)
    {
        for (int j=i+1; j<10; j++) e.push_back({N+i, N+j});
        e.push_back({N+i, N+11});
    }
    for (int i=0; i<N; i++) e.push_back({i, N+10});
    e.push_back({N+10, N+11});
    InitG(N+12, e.size());
    for (int i=0; i<e.size(); i++)
    {
        //cerr<<e[i].first<<' '<<e[i].second<<endl;
        MakeG(i, e[i].first, e[i].second);
    }
}

Bob

#include "Boblib.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
using pii=pair<int, int>;

void InitMap(int N, int M);
void MakeMap(int A, int B);

const int MN=1013;
int deg[MN], rep[MN];
bool f[MN];

void Bob(int V, int U, int C[], int D[])
{
    for (int i=0; i<V; i++) deg[i]=rep[i]=f[i]=0;
    for (int i=0; i<U; i++)
    {
        deg[C[i]]++;
        deg[D[i]]++;
    }
    int n=V-12, rt=-1, dum=-1;
    for (int i=0; i<U; i++)
    {
        if (deg[C[i]]==n+1 && deg[D[i]]==11)
        {
            rt=C[i];
            dum=D[i];
            break;
        }
        if (deg[D[i]]==n+1 && deg[C[i]]==11)
        {
            rt=D[i];
            dum=C[i];
            break;
        }
    }
    assert(rt!=-1);
    //cerr<<rt<<' '<<dum<<endl;
    for (int i=0; i<U; i++)
    {
        if (C[i]==rt && D[i]!=dum)
        {
            assert(D[i]!=rt);
            f[D[i]]=1;
        }
        if (D[i]==rt && C[i]!=dum)
        {
            assert(C[i]!=rt);
            f[C[i]]=1;
        }
    }
    vector<int> vec;
    for (int i=0; i<V; i++) if (!f[i] && i!=rt && i!=dum) vec.push_back(i);
    assert(vec.size()==10);
    sort(vec.begin(), vec.end(), [](int x, int y) { return deg[x]>deg[y]; });
    for (int i=0; i<10; i++) rep[vec[i]]=i;
    for (int i=0; i<U; i++)
    {
        if ((!f[C[i]] && C[i]!=rt && C[i]!=dum) && f[D[i]])
        {
            assert(!((rep[D[i]]>>rep[C[i]])&1));
            rep[D[i]]^=(1<<rep[C[i]]);
        }
        if ((!f[D[i]] && D[i]!=rt && D[i]!=dum) && f[C[i]])
        {
            assert(!((rep[C[i]]>>rep[D[i]])&1));
            rep[C[i]]^=(1<<rep[D[i]]);
        }
    }
    vector<pii> e;
    for (int i=0; i<U; i++)
    {
        if (f[C[i]] && f[D[i]])
        {
            e.push_back({rep[C[i]], rep[D[i]]});
        }
    }
    InitMap(n, e.size());
    for (auto [u, v]:e) MakeMap(u, v);
}

• 서브태스크 1: 0 / 22
• 서브태스크 2: 0 / 15
• 서브태스크 3: 0 / 63