oj.uz

Submission #218454

# Submission time Handle Problem Language Result Execution time Memory
218454 2020-04-02T07:45:29 Z extraterrestrial Airline Route Map (JOI18_airline) C++14
0 / 100
 721 ms 31168 KB 
#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);
  }
}


#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 31168 KB Output is correct : V - N = 12
2 Correct 528 ms 25708 KB Output is correct : V - N = 12
3 Correct 225 ms 14020 KB Output is correct : V - N = 12
4 Correct 22 ms 7424 KB Output is correct : V - N = 12
5 Correct 143 ms 11328 KB Output is correct : V - N = 12
6 Correct 432 ms 23812 KB Output is correct : V - N = 12
7 Correct 659 ms 30408 KB Output is correct : V - N = 12
8 Correct 604 ms 27824 KB Output is correct : V - N = 12
9 Correct 309 ms 17360 KB Output is correct : V - N = 12
10 Correct 48 ms 8424 KB Output is correct : V - N = 12
11 Correct 74 ms 9184 KB Output is correct : V - N = 12
12 Correct 349 ms 19152 KB Output is correct : V - N = 12
13 Correct 623 ms 29128 KB Output is correct : V - N = 12
14 Correct 648 ms 29608 KB Output is correct : V - N = 12
15 Correct 401 ms 22816 KB Output is correct : V - N = 12
16 Correct 122 ms 9952 KB Output is correct : V - N = 12
17 Correct 33 ms 7664 KB Output is correct : V - N = 12
18 Correct 249 ms 15768 KB Output is correct : V - N = 12
19 Correct 542 ms 26912 KB Output is correct : V - N = 12
20 Correct 650 ms 30872 KB Output is correct : V - N = 12
21 Correct 183 ms 13272 KB Output is correct : V - N = 12
22 Correct 141 ms 11992 KB Output is correct : V - N = 12
23 Correct 66 ms 8936 KB Output is correct : V - N = 12
24 Correct 16 ms 6912 KB Output is correct : V - N = 12
25 Correct 45 ms 8168 KB Output is correct : V - N = 12
26 Correct 133 ms 10968 KB Output is correct : V - N = 12
27 Correct 175 ms 13272 KB Output is correct : V - N = 12
28 Correct 167 ms 12512 KB Output is correct : V - N = 12
29 Correct 83 ms 9952 KB Output is correct : V - N = 12
30 Correct 19 ms 7424 KB Output is correct : V - N = 12
31 Correct 18 ms 7168 KB Output is correct : V - N = 12
32 Correct 18 ms 7168 KB Output is correct : V - N = 12
33 Correct 19 ms 7168 KB Output is correct : V - N = 12
34 Correct 19 ms 7168 KB Output is correct : V - N = 12
35 Correct 18 ms 7168 KB Output is correct : V - N = 12
36 Correct 689 ms 30688 KB Output is correct : V - N = 12
37 Correct 721 ms 30808 KB Output is correct : V - N = 12
38 Correct 688 ms 30608 KB Output is correct : V - N = 12
39 Correct 702 ms 30648 KB Output is correct : V - N = 12
40 Correct 665 ms 30600 KB Output is correct : V - N = 12
41 Correct 129 ms 11224 KB Output is correct : V - N = 12
42 Correct 107 ms 10456 KB Output is correct : V - N = 12
43 Correct 116 ms 10712 KB Output is correct : V - N = 12
44 Correct 19 ms 7168 KB Output is correct : V - N = 12
45 Correct 79 ms 9440 KB Output is correct : V - N = 12
46 Correct 229 ms 14800 KB Output is correct : V - N = 12
47 Correct 130 ms 10968 KB Output is correct : V - N = 12
48 Correct 311 ms 17616 KB Output is correct : V - N = 12
49 Correct 68 ms 8928 KB Output is correct : V - N = 12
50 Correct 31 ms 7680 KB Output is correct : V - N = 12
51 Correct 521 ms 26212 KB Output is correct : V - N = 12
52 Correct 20 ms 7424 KB Output is correct : V - N = 12
53 Correct 430 ms 23588 KB Output is correct : V - N = 12
54 Correct 596 ms 27592 KB Output is correct : V - N = 12
55 Correct 41 ms 8440 KB Output is correct : V - N = 12
56 Correct 356 ms 18616 KB Output is correct : V - N = 12
57 Correct 621 ms 29080 KB Output is correct : V - N = 12
58 Correct 107 ms 10208 KB Output is correct : V - N = 12
59 Correct 235 ms 15824 KB Output is correct : V - N = 12
60 Correct 645 ms 30008 KB Output is correct : V - N = 12
61 Correct 13 ms 6912 KB Output is correct : V - N = 12
62 Correct 13 ms 6912 KB Output is correct : V - N = 12
63 Correct 14 ms 6912 KB Output is correct : V - N = 12
64 Correct 13 ms 6912 KB Output is correct : V - N = 12
65 Correct 13 ms 6912 KB Output is correct : V - N = 12
66 Correct 13 ms 6912 KB Output is correct : V - N = 12
67 Correct 15 ms 6912 KB Output is correct : V - N = 12
68 Correct 13 ms 6912 KB Output is correct : V - N = 12
69 Correct 13 ms 6912 KB Output is correct : V - N = 12
70 Correct 13 ms 6912 KB Output is correct : V - N = 12
71 Correct 13 ms 6912 KB Output is correct : V - N = 12
72 Correct 13 ms 6912 KB Output is correct : V - N = 12
73 Correct 13 ms 6912 KB Output is correct : V - N = 12
74 Correct 13 ms 6912 KB Output is correct : V - N = 12
75 Correct 13 ms 6912 KB Output is correct : V - N = 12
76 Correct 13 ms 6912 KB Output is correct : V - N = 12
77 Correct 13 ms 6912 KB Output is correct : V - N = 12
78 Correct 13 ms 6912 KB Output is correct : V - N = 12
79 Correct 16 ms 6912 KB Output is correct : V - N = 12
80 Correct 13 ms 6912 KB Output is correct : V - N = 12
81 Correct 13 ms 6912 KB Output is correct : V - N = 12
82 Runtime error 15 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Halted 0 ms 0 KB -