Submission #388719

#	Time	Username	Problem	Language	Result	Execution time	Memory
388719		denkendoemeer	Airline Route Map (JOI18_airline)	C++14	100 / 100	822 ms	29388 KiB

Alice

#include<bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
void Alice(int n,int m,int a[],int b[])
{
    vector<pair<int,int>>ed;
    int i,j;
    for(i=0;i<m;i++)
        ed.emplace_back(a[i],b[i]);
    for(i=0;i<n;i++)
        for(j=0;j<10;j++)
            if (i>>j&1)
                ed.emplace_back(n+j,i);
    for(i=0;i<n;i++)
        ed.emplace_back(n+10,i);
    for(i=1;i<10;i++)
        ed.emplace_back(n+i-1,n+i);
    ed.emplace_back(n+11,n+10);
    InitG(n+12,ed.size());
    for(i=0;i<ed.size();i++)
        MakeG(i,ed[i].first,ed[i].second);
}

Bob

#include<bits/stdc++.h>
#include "Boblib.h"
using namespace std;
void Bob(int n,int m,int a[],int b[])
{
    vector<vector<int>>g(n);
    int i;
    for(i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    vector<bool>nr(n);
    int poz;
    for(i=0;i<n;i++)
        if (g[i].size()==1 && g[g[i][0]].size()==n-11){
            poz=g[i][0];
            for(auto it:g[poz])
                nr[it]=1;
            break;
        }
    int cur=poz;
    for(i=0;i<n;i++)
        if (i!=poz && nr[i]==0 && g[i].size()<=g[cur].size())
            cur=i;
    int pre=cur;
    vector<int>care(n);
    for(i=9;i>=0;i--){
        for(auto it:g[cur])
            if (nr[it])
                care[it]+=1<<i;
        for(auto it:g[cur])
            if (nr[it]==0 && it!=pre){
                pre=cur;
                cur=it;
                break;
            }
    }
    vector<pair<int,int>>ed;
    for(i=0;i<m;i++)
        if (nr[a[i]] && nr[b[i]])
            ed.emplace_back(care[a[i]],care[b[i]]);
    InitMap(n-12,ed.size());
    for(auto it:ed)
        MakeMap(it.first,it.second);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(i=0;i<ed.size();i++)
      |             ~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:15:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |         if (g[i].size()==1 && g[g[i][0]].size()==n-11){
      |                               ~~~~~~~~~~~~~~~~~^~~~~~
Bob.cpp:23:32: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |         if (i!=poz && nr[i]==0 && g[i].size()<=g[cur].size())
      |             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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