Submission #1177229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177229		simona1230	Airline Route Map (JOI18_airline)	C++17	100 / 100	169 ms	27112 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 cnte=0;

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

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

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

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

    InitG(N+12,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&&v[v[i][0]].size()==V-11)ed=i;

    ed=v[ed][0];
    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)
    {
        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(bt[i]!=-1)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: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63