Submission #232582

#	Time	Username	Problem	Language	Result	Execution time	Memory
232582		AlexLuchianov	Airline Route Map (JOI18_airline)	C++14	100 / 100	865 ms	31432 KiB

Alice

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

using namespace std;

void Alice( int n, int m, int A[], int B[] ){
	vector<pair<int, int>> edges;
  for(int i = 0;i < m; i++)
    edges.push_back({A[i], B[i]});
  //encryption nodes
  for(int j = 0; j < 9; j++)
    edges.push_back({n + j, n + j + 1});

  for(int i = 0; i < n; i++)
    for(int j = 0; j < 10; j++)
      if(0 < (i & (1 << j)))
        edges.push_back({i, n + j});

  for(int j = 0; j < 10; j++)
    edges.push_back({n + j, n + 10});
  for(int i = 0; i < n + 10; i++)
    edges.push_back({i, n + 11});


  InitG(n + 12, edges.size());
  for(int i = 0; i < edges.size(); i++) {
    MakeG(i, edges[i].first, edges[i].second);
  }
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int const nmax = 2000;
vector<int> g[1 + nmax];

int mex(vector<int> temp, int avoid){
  temp.push_back(avoid);
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++)
    if(temp[i] != i)
      return i;
  return temp.size();
}

int vanila[1 + nmax], id[1 + nmax];
int cost[1 + nmax];

int grad(int node){
  int result = 0;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    result += (0 < vanila[to]);
  }
  return result;
}

int nxt(int node){
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(vanila[to] == 1)
      return to;
  }
  return 0;
}

vector<int> extract(int node, int n){
  vector<int> temp;
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    vanila[to] = 1;
    temp.push_back(to);
  }

  int start = 0;

  for(int h = 0; h < temp.size(); h++){
    int to = temp[h];
    if(grad(to) == 3 && n / 2 + 2 + 1 == g[to].size())
      start = to;
  }

  vector<int> sol;
  sol.push_back(start);
  vanila[start] = 2;

  for(int h = 1; h < 10; h++){
    sol.push_back(nxt(sol.back()));
    vanila[sol.back()] = 2;
  }

  for(int h = 0; h < 10; h++)
    cost[sol[h]] = (1 << h);

  return sol;
}

void Bob( int n, int m, int C[], int D[] ){
  vector<pair<int,int>> sol;
  for(int i = 0; i < m; i++){
    int x = C[i];
    int y = D[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int decode1, decode2;
  for(int i = 0; i < n; i++)
    if(g[i].size() == n - 2)
      decode1 = i;

  decode2 = mex(g[decode1], decode1);
  vanila[decode1] = vanila[decode2] = 2;

  vector<int> enc = extract(decode2, n - 12);

  for(int i = 0; i < n; i++)
    if(vanila[i] == 0){
      for(int h = 0; h < g[i].size(); h++)
        id[i] += cost[g[i][h]];
    }


  for(int i = 0; i < m; i++){
    int x = C[i];
    int y = D[i];
    if(vanila[x] == 0 && vanila[y] == 0)
      sol.push_back({id[x], id[y]});
  }

  InitMap(n - 12, sol.size());
  for(int i = 0; i < sol.size(); i++)
    MakeMap(sol[i].first, sol[i].second);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < edges.size(); i++) {
                  ~~^~~~~~~~~~~~~~

Bob.cpp: In function 'int mex(std::vector<int>, int)':
Bob.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~
Bob.cpp: In function 'int grad(int)':
Bob.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
Bob.cpp: In function 'int nxt(int)':
Bob.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
Bob.cpp: In function 'std::vector<int> extract(int, int)':
Bob.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++) {
                  ~~^~~~~~~~~~~~~~~~
Bob.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < temp.size(); h++){
                  ~~^~~~~~~~~~~~~
Bob.cpp:56:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(grad(to) == 3 && n / 2 + 2 + 1 == g[to].size())
                         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(g[i].size() == n - 2)
        ~~~~~~~~~~~~^~~~~~~~
Bob.cpp:95:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[i].size(); h++)
                      ~~^~~~~~~~~~~~~
Bob.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sol.size(); i++)
                  ~~^~~~~~~~~~~~
Bob.cpp:83:7: warning: 'decode1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int decode1, decode2;
       ^~~~~~~

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