Submission #218454

#	Time	Username	Problem	Language	Result	Execution time	Memory
218454		extraterrestrial	Airline Route Map (JOI18_airline)	C++14	0 / 100	721 ms	31168 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

//InitG(n, m)
//MakeG(id, u, v)

void Alice(int N, int M, int A[], int B[]) {
	vector<pair<int, int>> edges;
  for (int i = 0; i < M; i++) {
    edges.pb({A[i], B[i]});
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < 10; j++) {
      if ((i >> j) & 1) {
        edges.pb({i - 1, N + j});
      }
    }
  }
  for (int j = 0; j < 9; j++) {
    edges.pb({N + j, N + j + 1});
  }
  for (int i = 0; i < 10; i++) {
    edges.pb({N + i, N + 10});
  }
  for (int i = 0; i < N + 10; i++) {
    edges.pb({i, N + 11});
  }
  InitG(N + 12, SZ(edges));
  for (int i = 0; i < SZ(edges); i++) {
    MakeG(i, edges[i].F, edges[i].S);
  }
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

void Bob(int V, int U, int C[], int D[]) {
  int n = V - 12;
  pair<int, int> mx;
  vector<int> cnt(V);
  vector<vector<int>> g(V);
  for (int i = 0; i < U; i++) {
    cnt[C[i]]++;
    cnt[D[i]]++;
    g[C[i]].pb(D[i]);
    g[D[i]].pb(C[i]);
  }
  for (int i = 0; i < V; i++) {
    mx = max(mx, make_pair(cnt[i], i));
  }
  assert(mx.F == n + 10);
  vector<bool> used(V);
  for (auto it : g[mx.S]) {
    used[it] = true;
  }
  int id = -1;
  for (int i = 0; i < V; i++) {
    if (!used[i] && i != mx.S) {
      id = i;
    }
  }
  assert(id != -1);
  fill(all(used), true);
  used[id] = false;
  used[mx.S] = false;
  for (auto it : g[id]) {
    used[it] = false;
  }
  int fst = -1;
  for (int i = 0; i < V; i++) {
    if (!used[i] && i != id && i != mx.S) {
      int cc = 0;
      for (auto it : g[i]) {
        if (!used[it] && it != id && it != mx.S) {
          cc++;
        }
      }
      if (cc == 1) {
        fst = i;
        break;
      }
    }
  }
  int prv = 0, cur = fst;
  vector<int> path = {cur};
  for (int i = 0; i < 9; i++) {
    for (auto it : g[cur]) {
      if (!used[it] && it != id && it != mx.S && it != prv) {
        path.pb(it);
        prv = cur;
        cur = it;
        break;
      }
    }
  }
  if (cnt[path[0]] < cnt[path.back()]) {
    reverse(all(path));
  }
  vector<vector<bool>> ok(10, vector<bool>(V));
  for (int i = 0; i < 10; i++) {
    for (auto it : g[path[i]]) {
      ok[i][it] = true;
    }
  }
  vector<pair<int, int>> rez;
  vector<int> go(V);
  for (int i = 0; i < V; i++) {
    if (used[i]) {
      int vl = 0;
      for (int j = 0; j < 10; j++) {
        if (ok[j][i]) {
          vl += 1 << j;
        }
      }
      vl--;
      go[i] = vl;
    }
  }
  for (int i = 0; i < U; i++) {
    if (used[C[i]] && used[D[i]]) {
      rez.pb({go[C[i]], go[D[i]]});
    }
  }
  InitMap(n, SZ(rez));
  for (auto it : rez) {
    MakeMap(it.F, it.S);
  }  
}

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