Submission #1177174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177174		simona1230	Airline Route Map (JOI18_airline)	C++17	22 / 100	43 ms	11152 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>

void Alice( int N, int M, int A[], int B[] )
{
    int cntv=0,cnte=0;
	for(int i=0;i<M;i++)
    {
        cntv+=A[i];
        cntv+=B[i];
        cntv+=6;

        cnte+=A[i];
        cnte+=B[i];
        cnte+=7;
    }
    InitG(cntv+N,cnte);
    int idv=0,ide=0;
    for(int i=0;i<M;i++)
    {
        int x=idv;

        for(int j=idv+1;j<=idv+A[i]+2;j++)
            MakeG(ide++,j-1,j);
        MakeG(ide++,idv+A[i]+2,idv);

        idv=idv+A[i]+3;
        int y=idv;

        for(int j=idv+1;j<=idv+B[i]+2;j++)
            MakeG(ide++,j-1,j);
        MakeG(ide++,idv+B[i]+2,idv);
        idv=idv+B[i]+3;

        MakeG(ide++,x,y);
    }
}

Bob

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

int _used[100000];
vector<int> v[100000];
int 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]);
    }

    int vr=0,ed=0;
    for(int i=0;i<V;i++)
        if(v[i].size()==0)vr++;

    vector<pair<int,int> > ans;
    for(int i=0;i<V;i++)
    {
        if(v[i].size()==2)continue;

        int p=-1,s=i,h=0;
        while(1)
        {
            _used[s]=1;
            int nxt=-1;
            for(int j=0;j<v[s].size();j++)
                if(!_used[v[s][j]]&&v[v[s][j]].size()==2)
                    nxt=v[s][j];
            if(nxt==-1)break;
            s=nxt;
            h++;
        }

        num[i]=h-2;
        for(int j=0;j<v[i].size();j++)
            if(_used[v[i][j]]&&v[v[i][j]].size()==3)
                ans.push_back({num[v[i][j]],num[i]});
    }

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

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