Submission #470138

#	Time	Username	Problem	Language	Result	Execution time	Memory
470138		dantoh000	Airline Route Map (JOI18_airline)	C++14	100 / 100	911 ms	29500 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
int d2[1025];
void Alice( int N, int M, int A[], int B[] ){
    vector<ii> E;
    for (int i = 0; i < M; i++){
        E.push_back({A[i],B[i]});
    }
    for (int i = 0; i < 10; i++){
        for (int j = 0; j < N; j++){
            if ((j>>(i))&1) E.push_back({j,N+i+1});
        }
        if (i!=9) E.push_back({N+i+1,N+i+2});
        E.push_back({N+i+1, N+11});
    }
    for (int i = 0; i <= N+10; i++){
        if (i != N) E.push_back({i,N});
    }
    for (auto v: E){
        //printf("%d %d\n",v.first,v.second);
    }
	InitG( N+12, E.size() );
	for (int i = 0; i < (int)E.size(); i++){
        MakeG(i, E[i].first, E[i].second);
        d2[E[i].first]++;
        d2[E[i].second]++;
	}
	/*for (int i = 0; i < N+12; i++){
        printf("d of %d = %d\n",i,d2[i]);
	}
	printf("\n");*/
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
int d[1025];
vector<int> G[1025];
int inP[1025];
int Label[1025];
int vis[1025];
void Bob( int V, int U, int C[], int D[] ){
    for (int i = 0; i < U; i++){
        d[C[i]]++;
        d[D[i]]++;
        G[C[i]].push_back(D[i]);
        G[D[i]].push_back(C[i]);
    }
    /*for (int i = 0; i < V; i++){
        printf("%d ",d[i]);
    }
    printf("\n");*/
    int maxd = 0;
    for (int i = 0; i < V; i++){
        if (d[i] > d[maxd]) maxd = i;
    }
    //printf("maxd %d\n",maxd);
    sort(G[maxd].begin(),G[maxd].end());
    vector<int> P;
    int j = 0;
    int missing = -1;
    for (int i = 0; i < V; i++) inP[i] = 0;
    for (int i = 0; i < V; i++){
        if (G[maxd][j] != i){
            if (i != maxd) {
                missing = i;
            }
        }
        else j++;
    }
    //printf("missing %d\n",missing);
    for (auto x : G[missing]){
        if (x != maxd){
            inP[x] = 1;
            P.push_back(x);
        }
    }
    int mindP = P[0];
    for (int i = 0; i < P.size(); i++){
        if (d[P[i]] < d[mindP]) mindP = P[i];
    }
    for (int i = 0; i < V; i++) {Label[i] = 0; vis[i] = -1;}
    int cur = mindP;
    vis[cur] = 1;

    for (int i = 0; i < 10; i++){
        Label[cur] = V-1-i;
        int mask = 1<<(9-i);
        for (auto x : G[cur]){
            Label[x] += mask;
        }
        for (auto x : G[cur]){
            if (vis[x] == -1 && inP[x]){
                vis[x] = 1;
                cur = x;
            }
        }
    }
    inP[maxd] = 1; inP[missing] = 1;
    /*for (int i = 0; i < V; i++){
        if (!inP[i]){
            printf("%d ",Label[i]);
        }
    }
    printf("\n");*/
    vector<ii> E;
    for (int i = 0; i < U; i++){
        if (!inP[C[i]] && !inP[D[i]]){
            E.emplace_back(Label[C[i]],Label[D[i]]);
        }
    }




	InitMap( V-12, (int)E.size() );
	for (auto x : E){
        MakeMap(x.first,x.second);
	}

}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:24:15: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   24 |     for (auto v: E){
      |               ^

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

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