제출 #1363240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363240		solution6312	항공 노선도 (JOI18_airline)	C++17	100 / 100	114 ms	26428 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<N; i++) e.push_back({i, N+10});
    for (int i=0; i<9; i++) e.push_back({N+i, N+i+1});
    for (int i=0; i<10; i++)
    {
        e.push_back({N+i, N+10});
        e.push_back({N+i, 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], f[MN], cnt[MN];
vector<int> g[MN];

void Bob(int V, int U, int C[], int D[])
{
    //cerr<<"HERE"<<endl;
    for (int i=0; i<V; i++)
    {
        deg[i]=rep[i]=f[i]=cnt[i]=0;
        g[i].clear();
    }
    for (int i=0; i<U; i++)
    {
        //cerr<<C[i]<<' '<<D[i]<<endl;
        g[C[i]].push_back(D[i]);
        g[D[i]].push_back(C[i]);
        deg[C[i]]++;
        deg[D[i]]++;
    }
    int n=V-12, rt=0;
    for (int i=1; i<n+12; i++) if (deg[i]>deg[rt]) rt=i;
    assert(deg[rt]==n+10);
    f[rt]=1;
    for (int i:g[rt]) f[i]=1;
    int dum=-1;
    for (int i=0; i<n+12; i++)
    {
        if (!f[i])
        {
            assert(dum==-1);
            dum=i;
        }
    }
    assert(dum!=-1);
    for (int i:g[rt]) f[i]=1;
    for (int i:g[dum]) f[i]=2;
    f[dum]=3; f[rt]=4;
    for (int i=0; i<U; i++)
    {
        if (f[C[i]]==2 && f[D[i]]==2)
        {
            cnt[C[i]]++;
            cnt[D[i]]++;
        }
    }
    vector<int> vec;
    for (int i:g[dum])
    {
        if (cnt[i]==1)
        {
            if (!vec.size()) vec.push_back(i);
            else if (deg[i]>deg[vec[0]])
            {
                vec.pop_back();
                vec.push_back(i);
            }
        }
    }
    for (int i=0; i<9; i++)
    {
        for (int j:g[vec[i]])
        {
            if (f[j]==2 && (i==0 || j!=vec[i-1]))
            {
                vec.push_back(j);
                break;
            }
        }
    }
    for (int i=0; i<10; i++)
    {
        for (int j:g[vec[i]])
        {
            if (f[j]==1)
            {
                assert(!((rep[j]>>i)&1));
                rep[j]^=(1<<i);
            }
        }
    }
    vector<pii> e;
    for (int i=0; i<U; i++)
    {
        if (f[C[i]]==1 && f[D[i]]==1)
        {
            e.push_back({rep[C[i]], rep[D[i]]});
        }
    }
    InitMap(n, e.size());
    for (auto [u, v]:e) MakeMap(u, v);
}

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