Submission #926217

#	Time	Username	Problem	Language	Result	Execution time	Memory
926217		Tuanlinh123	Airline Route Map (JOI18_airline)	C++17	100 / 100	500 ms	39676 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

void Alice(ll n, ll m, ll A[], ll B[])
{
    vector <pll> ans;
    for (ll i=0; i<m; i++)
        ans.pb({A[i], B[i]});
    for (ll i=0; i<10; i++)
    {
        for (ll j=0; j<n; j++)
            if (j&1<<i)
                ans.pb({n+i, j});
        if (i) ans.pb({n+i, n+i-1});
    }
    for (ll j=0; j<n; j++)
        ans.pb({n+10, j});
    for (ll j=0; j<n; j++)
        ans.pb({n+11, j});
    InitG(n+12, ans.size());
    for (ll i=0; i<ans.size(); i++)
        MakeG(i, ans[i].fi, ans[i].se);
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;


void Bob(ll v, ll e, ll U[], ll V[])
{
    ll n=v-12, base=1009, Mod=1e9+7;
    vector <vector <ll>> A(v);
    for (ll i=0; i<e; i++)
        A[U[i]].pb(V[i]), A[V[i]].pb(U[i]);
    ll root=0;
    map <long long, vector <ll>> hash;
    for (ll i=0; i<v; i++)
        if (A[i].size()==n)
        {
            sort(A[i].begin(), A[i].end());
            long long key=0;
            for (ll j:A[i])
                key=(key+j)*base%Mod;
            hash[key].pb(i);
        }
    for (pair<ll, vector <ll>> i:hash)
        if (i.se.size()==2)
            root=i.se[0];
    vector <ll> check(v, 0), idx(v, 0);
    for (ll i:A[root]) check[i]=1;
    vector <ll> line;
    pll first={1e9, 1e9};
    for (ll i=0; i<v; i++)
        if (!check[i])
            first=min(first, {A[i].size(), i});
    line.pb(first.se);
    while (1)
    {
        ll cand=-1;
        for (ll j:A[line.back()])
            if (!check[j] && (line.size()==1 || j!=line[line.size()-2]))
                {cand=j; break;}
        if (cand==-1) break;
        line.pb(cand);
    }
    reverse(line.begin(), line.end());
    for (ll i=0; i<line.size(); i++)
        for (ll j:A[line[i]])
            if (check[j])
                idx[j]|=1<<i;
    vector <pll> ans;
    for (ll i=0; i<e; i++)
        if (check[U[i]] && check[V[i]])
            ans.pb({idx[U[i]], idx[V[i]]});
    InitMap(n, ans.size());
    for (pll i:ans) MakeMap(i.fi, i.se);
}

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:22:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         if (A[i].size()==n)
      |             ~~~~~~~~~~~^~~
Bob.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (ll i=0; i<line.size(); i++)
      |                  ~^~~~~~~~~~~~

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