Submission #48298

#	Time	Username	Problem	Language	Result	Execution time	Memory
48298		marvenlee	Airline Route Map (JOI18_airline)	C++14	0 / 100	2527 ms	1048576 KiB

Alice

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

void Alice( int N, int M, int A[], int B[] )
{
	vector<int> newA;
	vector<int> newB;
	int newedge=1;
	newA.push_back(1);
	newB.push_back(N);
	for(int i=2;i<N;i++)
    {
        int x=i;
        int y=0;
        while(x!=1)
        {
            if(x%2==1)
            {
                    newA.push_back(i);
                    newB.push_back(N+y);
                    newedge+=1;
                    x/=2;
                    y++;
            }
            newA.push_back(i);
            newB.push_back(N+y);
            newedge+=1;
        }
    }
    newedge+=29;
    for(int i=0;i<9;i++)
    {
        newA.push_back(N+i);
        newB.push_back(N+i+1);

        newA.push_back(N+i);
        newB.push_back(N+10);

        newA.push_back(N+i);
        newB.push_back(N+11);
    }
    newA.push_back(N+9);
    newB.push_back(N+10);

    newA.push_back(N+9);
    newB.push_back(N+11);
	InitG( N+12, M+newedge);
	for(int i=0;i<M;i++) MakeG(i, A[i], B[i] );
    for(int i=0;i<newedge;i++) MakeG(i+M, newA[i], newB[i] );
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
void Bob( int V, int U, int C[], int D[] )
{
    vector<vector<int> > findbit(V,vector<int>());
    vector<vector<int> > findedge(V,vector<int>());
    vector<int> probablybit;
    int edgecount=0;
    for(int i=0;i<U;i++)
    {
        findedge[C[i]].push_back(D[i]);
        findbit[D[i]].push_back(C[i]);
    }
    for(int i=0;i<V;i++)
    {
        if(findbit[i].size()==10) probablybit.push_back(i);
        sort(findbit[i].begin(),findbit[i].end());
    }

    int extra1,extra2;
    vector<int> bitmap;
    vector<int> probably;
    for(int i=0;i<probablybit.size();i++)
    {
        for(int j=i+1;j<probablybit.size();j++)
        {
            if(findbit[probablybit[i]]==findbit[probablybit[j]])
            {
                extra1=probablybit[i];
                extra2=probablybit[j];
                i=probablybit.size();
                probably=findbit[probablybit[j]];
                break;
            }
        }
    }

    vector<ii> connectbit(V);
    for(int i=0;i<10;i++)
    {
        int a=probably[i];
        for(int j=0;j<10,j!=i;j++)
        {
            int b = probably[j];
            for(int z=0;z<findedge[a].size();z++)
            {
                if(findedge[a][z]==b)
                {
                   connectbit.push_back(ii(a,b));
                }
                if(connectbit.size()==9)break;
            }
            if(connectbit.size()==9)break;
        }
        if(connectbit.size()==9)break;
    }
    vector<int> bit;
    bit.push_back(connectbit[0].first);
    bit.push_back(connectbit[0].second);
    connectbit.erase(connectbit.begin());
    while(bit.size()!=10)
    {
        for(int i=0;i<bit.size();i++)
        {
            if(connectbit[i].first==bit.back())
            {
                bit.push_back(connectbit[i].second);
                connectbit.erase(connectbit.begin()+i);
            }
            else if(connectbit[i].second==bit[0])
            {
                bit.insert(bit.begin(),connectbit[i].first);
            }
        }
    }
    vector<int> actual;
    actual.assign(V,-1);
    if(bit[0]>bit[9]) reverse(bit.begin(),bit.end());
    for(int i=0;i<U;i++)
    {
        int actualvalue=0;
        for(int j=0;j<findbit[C[i]].size();j++)
        {

            for(int x=0;x<10;x++)
            {
                if(C[i]==bit[x]||C[i]==extra1||C[i]==extra2)
                {
                    j=findbit[C[i]].size();
                    break;
                }
                if(findbit[C[i]][j]==bit[x])
                {
                    actualvalue+=pow(2,x);
                    break;
                }

            }
            if(j==findbit[C[i]].size()-1 && actualvalue==0) actualvalue=-1;
        }
        if(actualvalue!=0)
        {
            if (actualvalue!=-1)
            actual[C[i]]=actualvalue;
            else
                actual[C[i]]=0;
        }
    }
    vector<int> A;
    vector<int> B;
    for(int i=0;i<U;i++)
    {
        if(actual[C[i]]!=-1)
        {
            if(actual[D[i]]!=-1)
            {
                A.push_back(actual[C[i]]);
                B.push_back(actual[D[i]]);
                edgecount+=1;
            }
        }
    }
	InitMap( V-12, edgecount );
	for(int i=0;i<edgecount;i++)
    {
        MakeMap(A[i],B[i]);
    }

}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<probablybit.size();i++)
                 ~^~~~~~~~~~~~~~~~~~~
Bob.cpp:29:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i+1;j<probablybit.size();j++)
                       ~^~~~~~~~~~~~~~~~~~~
Bob.cpp:46:22: warning: left operand of comma operator has no effect [-Wunused-value]
         for(int j=0;j<10,j!=i;j++)
                     ~^~~
Bob.cpp:49:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int z=0;z<findedge[a].size();z++)
                         ~^~~~~~~~~~~~~~~~~~~
Bob.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<bit.size();i++)
                     ~^~~~~~~~~~~
Bob.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<findbit[C[i]].size();j++)
                     ~^~~~~~~~~~~~~~~~~~~~~
Bob.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j==findbit[C[i]].size()-1 && actualvalue==0) actualvalue=-1;
                ~^~~~~~~~~~~~~~~~~~~~~~~~
Bob.cpp:24:16: warning: 'extra2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int extra1,extra2;
                ^~~~~~
Bob.cpp:24:9: warning: 'extra1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int extra1,extra2;
         ^~~~~~

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