oj.uz

Submission #930059

# Submission time Handle Problem Language Result Execution time Memory
930059 2024-02-18T11:46:20 Z nguyentunglam Airline Route Map (JOI18_airline) C++17
0 / 100
 474 ms 52012 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 = 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

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 Correct 3 ms 17916 KB Output is correct
3 Correct 2 ms 17920 KB Output is correct
4 Correct 3 ms 15620 KB Output is correct
5 Correct 2 ms 17668 KB Output is correct
6 Correct 3 ms 17668 KB Output is correct
7 Correct 3 ms 17676 KB Output is correct
8 Correct 3 ms 17664 KB Output is correct
9 Correct 2 ms 17668 KB Output is correct
10 Correct 2 ms 15620 KB Output is correct
11 Correct 2 ms 17668 KB Output is correct
12 Correct 3 ms 17668 KB Output is correct
13 Correct 2 ms 17664 KB Output is correct
14 Correct 3 ms 17668 KB Output is correct
15 Correct 2 ms 17668 KB Output is correct
16 Correct 2 ms 17668 KB Output is correct
17 Correct 2 ms 17668 KB Output is correct
18 Correct 3 ms 17668 KB Output is correct
19 Correct 2 ms 17668 KB Output is correct
20 Correct 2 ms 17664 KB Output is correct
21 Correct 2 ms 17668 KB Output is correct
22 Correct 3 ms 17672 KB Output is correct
23 Correct 2 ms 17664 KB Output is correct
24 Correct 2 ms 15616 KB Output is correct
25 Correct 2 ms 17664 KB Output is correct
26 Correct 2 ms 17664 KB Output is correct
27 Correct 2 ms 17664 KB Output is correct
28 Correct 3 ms 17660 KB Output is correct
29 Correct 2 ms 17664 KB Output is correct
30 Correct 2 ms 15620 KB Output is correct
31 Correct 2 ms 15620 KB Output is correct
32 Correct 2 ms 15620 KB Output is correct
33 Correct 3 ms 15616 KB Output is correct
34 Correct 2 ms 15620 KB Output is correct
35 Correct 2 ms 15620 KB Output is correct
36 Correct 2 ms 17668 KB Output is correct
37 Correct 2 ms 17672 KB Output is correct
38 Correct 3 ms 17664 KB Output is correct
39 Correct 3 ms 17668 KB Output is correct
40 Correct 2 ms 17668 KB Output is correct
41 Correct 3 ms 17672 KB Output is correct
42 Correct 2 ms 17660 KB Output is correct
43 Correct 2 ms 17664 KB Output is correct
44 Correct 2 ms 15620 KB Output is correct
45 Correct 2 ms 15620 KB Output is correct
46 Runtime error 7 ms 24324 KB Execution killed with signal 6
47 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 Correct 3 ms 17916 KB Output is correct
3 Correct 2 ms 17920 KB Output is correct
4 Correct 3 ms 15620 KB Output is correct
5 Correct 2 ms 17668 KB Output is correct
6 Correct 3 ms 17668 KB Output is correct
7 Correct 3 ms 17676 KB Output is correct
8 Correct 3 ms 17664 KB Output is correct
9 Correct 2 ms 17668 KB Output is correct
10 Correct 2 ms 15620 KB Output is correct
11 Correct 2 ms 17668 KB Output is correct
12 Correct 3 ms 17668 KB Output is correct
13 Correct 2 ms 17664 KB Output is correct
14 Correct 3 ms 17668 KB Output is correct
15 Correct 2 ms 17668 KB Output is correct
16 Correct 2 ms 17668 KB Output is correct
17 Correct 2 ms 17668 KB Output is correct
18 Correct 3 ms 17668 KB Output is correct
19 Correct 2 ms 17668 KB Output is correct
20 Correct 2 ms 17664 KB Output is correct
21 Correct 2 ms 17668 KB Output is correct
22 Correct 3 ms 17672 KB Output is correct
23 Correct 2 ms 17664 KB Output is correct
24 Correct 2 ms 15616 KB Output is correct
25 Correct 2 ms 17664 KB Output is correct
26 Correct 2 ms 17664 KB Output is correct
27 Correct 2 ms 17664 KB Output is correct
28 Correct 3 ms 17660 KB Output is correct
29 Correct 2 ms 17664 KB Output is correct
30 Correct 2 ms 15620 KB Output is correct
31 Correct 2 ms 15620 KB Output is correct
32 Correct 2 ms 15620 KB Output is correct
33 Correct 3 ms 15616 KB Output is correct
34 Correct 2 ms 15620 KB Output is correct
35 Correct 2 ms 15620 KB Output is correct
36 Correct 2 ms 17668 KB Output is correct
37 Correct 2 ms 17672 KB Output is correct
38 Correct 3 ms 17664 KB Output is correct
39 Correct 3 ms 17668 KB Output is correct
40 Correct 2 ms 17668 KB Output is correct
41 Correct 3 ms 17672 KB Output is correct
42 Correct 2 ms 17660 KB Output is correct
43 Correct 2 ms 17664 KB Output is correct
44 Correct 2 ms 15620 KB Output is correct
45 Correct 2 ms 15620 KB Output is correct
46 Runtime error 7 ms 24324 KB Execution killed with signal 6
47 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 40712 KB Output is correct : V - N = 12
2 Correct 409 ms 40592 KB Output is correct : V - N = 12
3 Correct 136 ms 23452 KB Output is correct : V - N = 12
4 Correct 7 ms 18180 KB Output is correct : V - N = 12
5 Correct 100 ms 21076 KB Output is correct : V - N = 12
6 Correct 286 ms 39456 KB Output is correct : V - N = 12
7 Correct 461 ms 40292 KB Output is correct : V - N = 12
8 Correct 427 ms 39796 KB Output is correct : V - N = 12
9 Correct 203 ms 24216 KB Output is correct : V - N = 12
10 Correct 25 ms 19312 KB Output is correct : V - N = 12
11 Correct 34 ms 19648 KB Output is correct : V - N = 12
12 Correct 283 ms 30316 KB Output is correct : V - N = 12
13 Correct 391 ms 40424 KB Output is correct : V - N = 12
14 Correct 460 ms 41272 KB Output is correct : V - N = 12
15 Correct 264 ms 36940 KB Output is correct : V - N = 12
16 Correct 71 ms 20140 KB Output is correct : V - N = 12
17 Correct 12 ms 18700 KB Output is correct : V - N = 12
18 Correct 190 ms 23696 KB Output is correct : V - N = 12
19 Correct 370 ms 40988 KB Output is correct : V - N = 12
20 Correct 474 ms 40536 KB Output is correct : V - N = 12
21 Correct 108 ms 21988 KB Output is correct : V - N = 12
22 Correct 91 ms 20676 KB Output is correct : V - N = 12
23 Correct 35 ms 19164 KB Output is correct : V - N = 12
24 Correct 5 ms 17668 KB Output is correct : V - N = 12
25 Correct 21 ms 18916 KB Output is correct : V - N = 12
26 Correct 82 ms 20512 KB Output is correct : V - N = 12
27 Correct 107 ms 21096 KB Output is correct : V - N = 12
28 Correct 91 ms 20704 KB Output is correct : V - N = 12
29 Correct 47 ms 19792 KB Output is correct : V - N = 12
30 Correct 6 ms 18148 KB Output is correct : V - N = 12
31 Correct 6 ms 16132 KB Output is correct : V - N = 12
32 Correct 6 ms 16136 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 16128 KB Output is correct : V - N = 12
36 Runtime error 423 ms 52012 KB Execution killed with signal 6
37 Halted 0 ms 0 KB -