oj.uz

Submission #930052

# Submission time Handle Problem Language Result Execution time Memory
930052 2024-02-18T11:03:18 Z nguyentunglam Airline Route Map (JOI18_airline) C++17
0 / 100
 495 ms 42152 KB 
#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]);
}


#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];

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 < 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]]);
//      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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17668 KB Output is correct
2 Runtime error 9 ms 24320 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17668 KB Output is correct
2 Runtime error 9 ms 24320 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 41812 KB Output is correct : V - N = 12
2 Correct 329 ms 40728 KB Output is correct : V - N = 12
3 Correct 124 ms 23692 KB Output is correct : V - N = 12
4 Correct 9 ms 18180 KB Output is correct : V - N = 12
5 Correct 78 ms 20768 KB Output is correct : V - N = 12
6 Correct 328 ms 39488 KB Output is correct : V - N = 12
7 Correct 485 ms 41096 KB Output is correct : V - N = 12
8 Correct 403 ms 41332 KB Output is correct : V - N = 12
9 Correct 245 ms 24700 KB Output is correct : V - N = 12
10 Correct 23 ms 19196 KB Output is correct : V - N = 12
11 Correct 41 ms 19892 KB Output is correct : V - N = 12
12 Correct 243 ms 30592 KB Output is correct : V - N = 12
13 Correct 374 ms 40520 KB Output is correct : V - N = 12
14 Correct 456 ms 40972 KB Output is correct : V - N = 12
15 Correct 275 ms 35756 KB Output is correct : V - N = 12
16 Correct 69 ms 20156 KB Output is correct : V - N = 12
17 Correct 12 ms 18948 KB Output is correct : V - N = 12
18 Correct 146 ms 23700 KB Output is correct : V - N = 12
19 Correct 357 ms 39880 KB Output is correct : V - N = 12
20 Correct 420 ms 40804 KB Output is correct : V - N = 12
21 Correct 128 ms 21932 KB Output is correct : V - N = 12
22 Correct 95 ms 20648 KB Output is correct : V - N = 12
23 Correct 36 ms 19588 KB Output is correct : V - N = 12
24 Correct 4 ms 17664 KB Output is correct : V - N = 12
25 Correct 20 ms 18904 KB Output is correct : V - N = 12
26 Correct 91 ms 20376 KB Output is correct : V - N = 12
27 Correct 110 ms 20948 KB Output is correct : V - N = 12
28 Correct 96 ms 20844 KB Output is correct : V - N = 12
29 Correct 47 ms 19404 KB Output is correct : V - N = 12
30 Correct 7 ms 18176 KB Output is correct : V - N = 12
31 Correct 6 ms 16124 KB Output is correct : V - N = 12
32 Correct 6 ms 16132 KB Output is correct : V - N = 12
33 Correct 6 ms 16132 KB Output is correct : V - N = 12
34 Correct 6 ms 16132 KB Output is correct : V - N = 12
35 Correct 6 ms 16384 KB Output is correct : V - N = 12
36 Correct 495 ms 41960 KB Output is correct : V - N = 12
37 Correct 408 ms 41312 KB Output is correct : V - N = 12
38 Correct 429 ms 41528 KB Output is correct : V - N = 12
39 Correct 453 ms 41244 KB Output is correct : V - N = 12
40 Correct 452 ms 42152 KB Output is correct : V - N = 12
41 Correct 67 ms 20952 KB Output is correct : V - N = 12
42 Correct 54 ms 20304 KB Output is correct : V - N = 12
43 Correct 85 ms 20932 KB Output is correct : V - N = 12
44 Correct 6 ms 18180 KB Output is correct : V - N = 12
45 Correct 56 ms 19640 KB Output is correct : V - N = 12
46 Correct 142 ms 23576 KB Output is correct : V - N = 12
47 Correct 71 ms 20924 KB Output is correct : V - N = 12
48 Correct 184 ms 24508 KB Output is correct : V - N = 12
49 Correct 34 ms 20912 KB Output is correct : V - N = 12
50 Correct 13 ms 19352 KB Output is correct : V - N = 12
51 Correct 409 ms 40608 KB Output is correct : V - N = 12
52 Correct 7 ms 18344 KB Output is correct : V - N = 12
53 Correct 307 ms 39652 KB Output is correct : V - N = 12
54 Correct 369 ms 40264 KB Output is correct : V - N = 12
55 Correct 22 ms 19220 KB Output is correct : V - N = 12
56 Correct 211 ms 29276 KB Output is correct : V - N = 12
57 Correct 464 ms 40184 KB Output is correct : V - N = 12
58 Correct 53 ms 20144 KB Output is correct : V - N = 12
59 Correct 154 ms 23808 KB Output is correct : V - N = 12
60 Correct 392 ms 41180 KB Output is correct : V - N = 12
61 Correct 3 ms 17668 KB Output is correct : V - N = 12
62 Correct 3 ms 17676 KB Output is correct : V - N = 12
63 Correct 2 ms 17668 KB Output is correct : V - N = 12
64 Runtime error 8 ms 24324 KB Execution killed with signal 6
65 Halted 0 ms 0 KB -