Submission #678186

#	Time	Username	Problem	Language	Result	Execution time	Memory
678186		ibm2006	Airline Route Map (JOI18_airline)	C++14	22 / 100	797 ms	42980 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,a[110000],b[110000],h[110000],x,y,s;
vector<ll> v[110000];
vector<pair<ll,ll>> p;
/*void InitG(ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    n=x;  m=y;
}
void MakeG(ll z,ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    v[x].push_back(y);
    v[y].push_back(x);
    h[x]++;
    h[y]++;
}*/
void Alice(ll N,ll M,ll A[],ll B[] ){
    if(N<=10)
    {
ll n,m,i,j;
//	vector<ll> v[1100];
	
	n=N+6;
	m=M;
	for(i=0;i<m;i++)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        s++;
        p.push_back({A[i],B[i]});
    }
    for(i=0;i<n;i++)
    {
        v[i].push_back(n);
        v[n].push_back(i);
        p.push_back({i,n});
        s++;
    }
    for(i=0;i<n;i++)
    {
        x=i;
        for(j=0;j<4;j++)
        {
            if(x%2==1)
            {
                if(j==0)
                {v[i].push_back(n+j+1);  s++;  v[n+j+1].push_back(i);
                p.push_back({i,n+j+1});
                 }
                v[i].push_back(n+j+2);
                v[n+j+2].push_back(i);
                s++;
                p.push_back({i,n+j+2});
            }
            x/=2;
        }
    }
    for(i=1;i<4;i++)
    {
        v[n+i+2].push_back(n+i+1);
        v[n+i+1].push_back(n+i+2);
        p.push_back({n+i+1,n+i+2});
        s++;
    }
    v[n+1].push_back(n+3);
    v[n+3].push_back(n+1);
    p.push_back({n+1,n+3});
    s++;
	InitG(n+6,s);
	for(i=0;i<s;i++)
        MakeG(i,p[i].first,p[i].second);
    return;
    ////////////////////////
    }
	ll n,m,i,j;
	//vector<ll> v[1100];
	//vector<pair<ll,ll>> p;
	n=N;
	m=M;
	for(i=0;i<m;i++)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        s++;
        p.push_back({A[i],B[i]});
    }
    for(i=0;i<n;i++)
    {
        v[i].push_back(n);
        v[n].push_back(i);
        p.push_back({i,n});
        s++;
    }
    for(i=0;i<n;i++)
    {
        x=i;
        for(j=0;j<10;j++)
        {
            if(x%2==1)
            {
                if(j==0)
                {v[i].push_back(n+j+1);  s++;  v[n+j+1].push_back(i);
                p.push_back({i,n+j+1});
                 }
                v[i].push_back(n+j+2);
                v[n+j+2].push_back(i);
                s++;
                p.push_back({i,n+j+2});
            }
            x/=2;
        }
    }
    for(i=1;i<10;i++)
    {
        v[n+i+2].push_back(n+i+1);
        v[n+i+1].push_back(n+i+2);
        p.push_back({n+i+1,n+i+2});
        s++;
    }
    v[n+1].push_back(n+3);
    v[n+3].push_back(n+1);
    p.push_back({n+1,n+3});
    s++;
	InitG(n+12,s);
	for(i=0;i<s;i++)
        MakeG(i,p[i].first,p[i].second);
    return;
}
/*int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%lld %lld",&a[i],&b[i]);
    }
    Alice(n,m,a,b);
    for(i=0;i<n;i++)
    {
        printf("%lld: ",i);
        x=v[i].size();
        for(j=0;j<x;j++)
            printf("%lld ",v[i][j]);
        printf("\n");
    }
}
*/

Bob

#include "Boblib.h"
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll b[1100][1100],n,m,i,a[110000],c[110000];
vector<ll> v[110000];
vector<pair<ll,ll>> p;
/*void InitMap(ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    n=x;  m=y;
}
void MakeMap(ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    v[x].push_back(y);
    v[y].push_back(x);
}*/
void Bob( int V, int U, int C[], int D[] ){
    ll j;
    ll n,m,s,a[11000],c[11000],d[11000],h[11000],t,x,y,i;
       n=0;  m=0;  s=0;  t=0;
       for(i=0;i<11000;i++)
       {a[i]=0;  c[i]=0;  d[i]=0;  h[i]=0;  t=0; x=0;  y=0;}
    if(V<=22)
    {

	vector<ll> u;
	n=V;
	m=U;
	s=n-6;
	//vector<ll> v[1100];
	
	for(i=0;i<m;i++)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
        b[C[i]][D[i]]=1;
        b[D[i]][C[i]]=1;
        h[C[i]]++;
        h[D[i]]++;
    }
    for(i=0;i<n;i++)
    {
        if(h[i]>=(s))
        {
            x=i;
            break;
        }
    }
  //  printf("%lld ",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
    a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        {
            u.push_back(i);
           // printf("%lld\n",i);
                   }
    }
    for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {//printf("%lld ",u[i]);
            if(b[u[i]][u[j]]==1)
                a[u[i]]++;
        }
   // printf("\n");
    }
    for(i=0;i<5;i++)
    {//printf("%lld ",a[u[i]]);
        if(a[u[i]]==3)
        {
            x=u[i];
            d[2]=x;
        }
    }
  //  printf("%lld\n",x);
    for(i=0;i<5;i++)
    {
        if(b[u[i]][d[2]]==1&&a[u[i]]==1)
            d[1]=u[i];
    }
    for(i=3;i<=3;i++)
    {
        for(j=0;j<5;j++)
        {
            if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==2)
                d[i]=u[j];
        }
    }
    i=4;
    for(j=0;j<5;j++)
    {
        if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==1)
                d[i]=u[j];
    }
  /*  for(i=1;i<=4;i++)
        printf("%lld ",d[i]);
   */ for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<n;i++)
    {
        if(h[i]>=s)
        {
            x=i;
            break;
        }
    }
 //   printf("%lld ",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
   // a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        continue;
    x=1;  y=0;
        for(j=1;j<=4;j++)
        {
            if(b[i][d[j]]==1)
                y+=x;
            x*=2;
        }
        c[i]=y;
    }
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
    {
        if(a[i]+a[j]<=1)
            continue;

        if(b[i][j]==1)
       {

       p.push_back({c[i],c[j]});

       t++;}
    }
    InitMap(s-6,t);
    for(i=0;i<t;i++)
    MakeMap(p[i].first,p[i].second);
        return;
    }
/*	InitMap( 3, 2 );
	MakeMap( 1, 2 );
	MakeMap( 1, 3 );*/

	vector<ll> u;
	n=V;
	m=U;
	s=n-12;
	//vector<ll> v[1100];
	//vector<pair<ll,ll>> p;
	for(i=0;i<m;i++)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
        b[C[i]][D[i]]=1;
        b[D[i]][C[i]]=1;
        h[C[i]]++;
        h[D[i]]++;
    }
    for(i=0;i<n;i++)
    {
        if(h[i]>=(s))
        {
            x=i;
            break;
        }
    }
  //  printf("%lld ",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
    a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        {
            u.push_back(i);
           // printf("%lld\n",i);
                   }
    }
    for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<11;i++)
    {
        for(j=0;j<11;j++)
        {//printf("%lld ",u[i]);
            if(b[u[i]][u[j]]==1)
                a[u[i]]++;
        }
   // printf("\n");
    }
    for(i=0;i<11;i++)
    {//printf("%lld ",a[u[i]]);
        if(a[u[i]]==3)
        {
            x=u[i];
            d[2]=x;
        }
    }
  //  printf("%lld\n",x);
    for(i=0;i<11;i++)
    {
        if(b[u[i]][d[2]]==1&&a[u[i]]==1)
            d[1]=u[i];
    }
    for(i=3;i<=9;i++)
    {
        for(j=0;j<11;j++)
        {
            if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==2)
                d[i]=u[j];
        }
    }
    i=10;
    for(j=0;j<11;j++)
    {
        if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==1)
                d[i]=u[j];
    }
  /*  for(i=1;i<=4;i++)
        printf("%lld ",d[i]);
   */ for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<n;i++)
    {
        if(h[i]>=s)
        {
            x=i;
            break;
        }
    }
 //   printf("%lld ",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
   // a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        continue;
    x=1;  y=0;
        for(j=1;j<=10;j++)
        {
            if(b[i][d[j]]==1)
                y+=x;
            x*=2;
        }
        c[i]=y;
    }
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
    {
        if(a[i]+a[j]<=1)
            continue;

        if(b[i][j]==1)
       {

       p.push_back({c[i],c[j]});

       t++;}
    }
    InitMap(s,t);
    for(i=0;i<t;i++)
    MakeMap(p[i].first,p[i].second);
        return;
}
/*int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%lld %lld",&a[i],&c[i]);
    }
    Bob(n,m,a,c);
}*/

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