Submission #930071

#	Time	Username	Problem	Language	Result	Execution time	Memory
930071		nguyentunglam	Airline Route Map (JOI18_airline)	C++17	100 / 100	565 ms	42696 KiB

Alice

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

const int NNN = 1e3 + 20;

int _deg[NNN];

void Alice( int n, int m, int a[], int b[] ){
  if (n == 1) {
    InitG(1, 0);
    return;
  }
	vector<pair<int, int> > e;

  for(int i = 0; i < m; i++) e.emplace_back(a[i], b[i]);

  for(int i = n; i < n + 10; i++) {
    e.emplace_back(i, n + 10);
    e.emplace_back(i, n + 11);
  }

  for(int i = n + 1; i < n + 10; i++) {
    e.emplace_back(i, i - 1);
  }

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

  InitG(n + 12, e.size());

  int cnt = 0;

  for(auto &[x, y] : e) {
    MakeG(cnt++, x, y);
    _deg[x]++;
    _deg[y]++;
  }

//  cout << _deg[n] << " " << _deg[n + 9] << " " << n << endl;
//  assert(_deg[n] != _deg[n + 9]);
}

Bob

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

const int NN = 1e3 + 20;

int deg[NN];

bool f[NN][NN];

bool R[NN];

int lab[NN];

int p[NN];

vector<int> adj[NN];

mt19937 rng(1);

void Bob( int n, int m, int c[], int d[] ){
  if (n == 1) {
    InitMap(1, 0);
    return;
  }
//  cout << n << " " << m << endl;

//  cout << endl;
//
//  for(int i = 0; i < m; i++) {
//    cout << c[i] << " " << d[i] << endl;
//  }

for(int i = 0; i < n; i++) lab[i] = i;
  random_shuffle(lab, lab + n);
  for(int i = 0; i < m; i++) {
    c[i] = lab[c[i]];
    d[i] = lab[d[i]];
  }
  for(int i = 0; i < n; i++) lab[i] = 0;

  for(int i = 0; i < m; i++) {
    if (rng() % 2) swap(c[i], d[i]);
//    cout << c[i] << " " << d[i] << endl;
  }

	for(int i = 0; i < m; i++) {
    deg[c[i]]++;
    deg[d[i]]++;
    adj[c[i]].push_back(d[i]);
    adj[d[i]].push_back(c[i]);
    f[c[i]][d[i]] = f[d[i]][c[i]] = 1;
	}

  for(int i = 0; i < n; i++) {
    sort(adj[i].begin(), adj[i].end());
  }

  int root = -1;

  for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) {
    if (adj[i].size() != 10) continue;
    if (adj[j].size() != 10) continue;
    if (adj[i] == adj[j]) {
      assert(root < 0);
      root = i;
      R[i] = R[j] = 1;
    }
  }

  assert(root >= 0);

  for(int &j : adj[root]) p[j] = 1;

  for(int &j : adj[root]) {
    for(int &k : adj[j]) if (p[k] && j < k) {
//      cout << j << " " << k << endl;
    }
  }

  int head = -1, found = 0;

  for(int &j : adj[root]) {
    int f_deg = 0;
    for(int &k : adj[j]) f_deg += p[k];
    if (f_deg == 1) {
      assert(++found <= 2);
      if (head != -1) assert(deg[j] != deg[head]);
      if (deg[j] > deg[head] || head == -1) head = j;
    }
  }

  assert(found);

  for(int loop = 2, x = head, pre = -1; loop <= 10; loop++) {
    found = 0;
    for(int k = 0; k < n; k++) if (k != pre && p[k] && f[x][k] && R[k] == 0) {
      pre = x;
      x = k;
      p[x] = loop;
      found = 1;
      break;
    }
    assert(found);
  }

  vector<pair<int, int> > e;

  for(int i = 0; i < m; i++) if (R[c[i]] == 0 && R[d[i]] == 0) {
    if (p[c[i]]) swap(c[i], d[i]);
    if (p[c[i]] == 0 && p[d[i]]) {
      lab[c[i]] |= 1 << p[d[i]] - 1;
    }
  }

  for(int i = 0; i < m; i++) if (R[c[i]] == 0 && R[d[i]] == 0) {
    if (p[c[i]] == 0 && p[d[i]] == 0) {
      e.emplace_back(lab[c[i]], lab[d[i]]);
//      cout << lab[c[i]] << " " << lab[d[i]] << endl;
//      cout << lab[c[i]] << " " << d[i] << endl;
    }
  }

  InitMap(n - 12, e.size());

  for(auto &[x, y] : e) MakeMap(x, y);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:114:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  114 |       lab[c[i]] |= 1 << p[d[i]] - 1;
      |                         ~~~~~~~~^~~

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