oj.uz

Submission #930050

# Submission time Handle Problem Language Result Execution time Memory
930050 2024-02-18T10:55:32 Z nguyentunglam Airline Route Map (JOI18_airline) C++17
0 / 100
 402 ms 51848 KB 
#include<bits/stdc++.h>
using namespace std;
#include "Alicelib.h"
#include <cassert>
#include <cstdio>

void Alice( int n, int m, int a[], int b[] ){
	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);
  }
}


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

const int NN = 1e3 + 10;

int deg[NN];

bool f[NN][NN];

bool R[NN];

int lab[NN];

int p[NN];

vector<int> adj[NN];

void Bob( int n, int m, int c[], int d[] ){

	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;

  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 = 0; loop <= 10; loop++) {
    found = 0;
    for(int k = 1; 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]]);
    }
  }

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

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

Compilation message

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 24252 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 24252 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 402 ms 51848 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -