제출 #1177211

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

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int> > ansa;
void Make(int i,int x,int y)
{
    ansa.push_back({x,y});
}

void Alice( int N, int M, int A[], int B[] )
{
    int b=0;
    while((1<<b)<=N)b++;
    int cnte=0;

    for(int i=0;i<M;i++)
        Make(cnte++,A[i]+1,B[i]+1);

    for(int i=0;i<b-1;i++)
        Make(cnte++,N+i+1,N+i+2);

    for(int i=1;i<=N;i++)
        Make(cnte++,i,N+b+1);
    Make(cnte++,N+b+1,0);

    for(int i=1;i<=N;i++)
        for(int j=0;j<b;j++)
            if(i&(1<<j))Make(cnte++,i,j+N+1);

    InitG(N+b+2,ansa.size());
    for(int i=0;i<ansa.size();i++)
        MakeG(i,ansa[i].first,ansa[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

int pw[100000],bt[100000];
vector<int> v[100000];
int done[100000],num[100000];
void Bob( int V, int U, int C[], int D[] )
{
    for(int i=0; i<U; i++)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
        //cout<<C[i]<<" "<<D[i]<<endl;
    }

    int ed=0;
    for(int i=0; i<V; i++)
        if(v[i].size()==1)ed=i;
    done[ed]=1;
    ed=v[ed][0];
    done[ed]=1;
    bt[ed]=-1;
    for(int i=0;i<v[ed].size();i++)
        bt[v[ed][i]]=-1;

    int f=-1,l=-1;
    for(int i=0;i<V;i++)
    {
        if(bt[i]==-1)continue;
        int in=0;
        for(int j=0;j<v[i].size();j++)
            if(bt[v[i][j]]==0)in++;

        if(in==1)
        {
            if(f!=-1)l=i;
            else f=i;
        }
    }
    if(v[f].size()<v[l].size())swap(f,l);
    int c=0;
    while(1)
    {
        done[f]=1;
        bt[f]=(1<<c);
        //cout<<f<<" > "<<(1<<c)<<endl;
        int h=0;
        for(int i=0;i<v[f].size();i++)
        {
            int nb=v[f][i];
            //cout<<nb<<" , ";
            if(!h&&bt[nb]==0)f=nb,h=1;
        }
        //cout<<endl;
        c++;
        if(h==0)break;
    }

    for(int i=0;i<V;i++)
    {
        if(done[i])continue;
        for(int j=0;j<v[i].size();j++)
        {
            int nb=v[i][j];
            if(bt[nb]!=-1)num[i]+=bt[nb];
        }
        //cout<<i<<" ! "<<num[i]<<endl;
    }

    vector<pair<int,int> > ansb;
    for(int i=0;i<U;i++)
    {
        if(num[C[i]]&&num[D[i]])
        {
            ansb.push_back({num[C[i]]-1,num[D[i]]-1});
        }
    }
    InitMap(V-c-2,ansb.size());

    for(int i=0;i<ansb.size();i++)
        MakeMap(ansb[i].first,ansb[i].second);
}

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