Submission #987004

#	Time	Username	Problem	Language	Result	Execution time	Memory
987004		cig32	Airline Route Map (JOI18_airline)	C++17	100 / 100	523 ms	39848 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include "bits/stdc++.h"
using namespace std;

void Alice( int N, int M, int A[], int B[] ){
  if(N == 1) {
    InitG(1, 0);
    return;
  }
  vector<pair<int, int>> edges;
  for(int i=0; i<M; i++) edges.push_back({A[i], B[i]});
  for(int i=0; i<N; i++) edges.push_back({i, N});
  for(int i=N+1; i<=N+10; i++) {
    edges.push_back({N, i});
    edges.push_back({N + 11, i});
  }
  for(int i=N+1; i<N+10; i++) {
    edges.push_back({i, i + 1});
  }
  edges.push_back({N + 2, N + 4});
  for(int i=0; i<N; i++) {
    for(int j=0; j<10; j++) {
      if(i & (1 << j)) {
        edges.push_back({i, N + 1 + j});
      }
    }
  }
  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 "bits/stdc++.h"
using namespace std;

void Bob( int V, int U, int C[], int D[] ){
	if(V == 1) {
    InitMap(1, 0);
    return;
  }
  vector<int> adj[V];
  for(int i=0; i<U; i++) {
    adj[C[i]].push_back(D[i]);
    adj[D[i]].push_back(C[i]);
  }
  int N = V - 12;

  int real[V];
  for(int i=0; i<V; i++ )real[i] = -1;
  vector<pair<int,int>> edges;

  int bit[V];
  for(int i=0; i<V; i++) bit[i] = -1;
  set<int> pp;
  for(int i=0; i<V; i++) {
    if(adj[i].size() == N + 10) {
      real[i] = N;
      int sum = 0;
      for(int j=0; j<V; j++) sum += j;
      for(int x: adj[i]) sum -= x;
      sum -= i;
      real[sum] = N + 11;
      for(int x: adj[sum]) {
        bit[x] = 0;
        pp.insert(x);
      }
      break;
    }
  }

  

  vector<int> partial[V];
  for(int i=0; i<U; i++) {
    if(bit[C[i]] == 0 && bit[D[i]] == 0) {
      partial[C[i]].push_back(D[i]);
      partial[D[i]].push_back(C[i]);
    }
  }
  for(int x: pp) {
    if(partial[x].size() == 1) {
      if(partial[partial[x][0]].size() == 3) {
        real[x] = N + 1;
        bit[x] = -1;
        real[partial[x][0]] = N + 2;
        bit[partial[x][0]] = -1;
        int nxt;
        for(int y: partial[partial[x][0]]) {
          if(partial[y].size() == 2) nxt = y;
        }
        real[nxt] = N + 3;
        bit[nxt] = -1;
        for(int i=N+4; i<=N+10; i++) {
          for(int y: partial[nxt]) {
            if(bit[y] == 0) {
              bit[y] = -1;
              real[y] = i;
              nxt = y;
              break;
            }
          }
        }
        break;
      }
    }
  }
  for(int i=0; i<V; i++) {
    if(real[i] == -1) {
      int s = 0;
      for(int x: adj[i]) {
        if(real[x] >= N + 1 && real[x] <= N + 10) {
          s |= (1ll << (real[x] - N - 1));
        }
      }
      real[i] = s;
    }
  }

  for(int i=0; i<U; i++) {
    if(real[C[i]] < N && real[D[i]] < N) {
      edges.push_back({real[C[i]], real[D[i]]});
    }
  }
  InitMap(N, edges.size());
  for(int i=0; i<edges.size(); i++) {
    MakeMap(edges[i].first, edges[i].second);
  }
  
}


/*
g++ -std=c++14 -O2 -o grader grader.cpp Alice.cpp Bob.cpp
./grader < input.txt
*/

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:27:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     if(adj[i].size() == N + 10) {
      |        ~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int i=0; i<edges.size(); i++) {
      |                ~^~~~~~~~~~~~~
Bob.cpp:63:18: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |         bit[nxt] = -1;
      |         ~~~~~~~~~^~~~

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