oj.uz

Submission #218460

# Submission time Handle Problem Language Result Execution time Memory
218460 2020-04-02T07:49:22 Z extraterrestrial Airline Route Map (JOI18_airline) C++14
0 / 100
 688 ms 31152 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));
  }
  if (mx.F != n + 10) {
    exit(0);
  }
  //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;
    }
  }
  if (id == -1) {
    exit(0);
  }
  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 Correct 13 ms 6912 KB Output is correct
2 Correct 13 ms 6912 KB Output is correct
3 Correct 13 ms 6912 KB Output is correct
4 Correct 13 ms 6656 KB Output is correct
5 Correct 13 ms 6912 KB Output is correct
6 Correct 13 ms 6912 KB Output is correct
7 Correct 13 ms 6912 KB Output is correct
8 Correct 13 ms 6912 KB Output is correct
9 Runtime error 20 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6912 KB Output is correct
2 Correct 13 ms 6912 KB Output is correct
3 Correct 13 ms 6912 KB Output is correct
4 Correct 13 ms 6656 KB Output is correct
5 Correct 13 ms 6912 KB Output is correct
6 Correct 13 ms 6912 KB Output is correct
7 Correct 13 ms 6912 KB Output is correct
8 Correct 13 ms 6912 KB Output is correct
9 Runtime error 20 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 30616 KB Output is correct : V - N = 12
2 Correct 533 ms 25896 KB Output is correct : V - N = 12
3 Correct 211 ms 14044 KB Output is correct : V - N = 12
4 Correct 20 ms 7536 KB Output is correct : V - N = 12
5 Correct 138 ms 11432 KB Output is correct : V - N = 12
6 Correct 464 ms 23768 KB Output is correct : V - N = 12
7 Correct 663 ms 30360 KB Output is correct : V - N = 12
8 Correct 608 ms 27848 KB Output is correct : V - N = 12
9 Correct 305 ms 17344 KB Output is correct : V - N = 12
10 Correct 44 ms 8440 KB Output is correct : V - N = 12
11 Correct 74 ms 9184 KB Output is correct : V - N = 12
12 Correct 352 ms 19152 KB Output is correct : V - N = 12
13 Correct 630 ms 28872 KB Output is correct : V - N = 12
14 Correct 628 ms 29552 KB Output is correct : V - N = 12
15 Correct 391 ms 22736 KB Output is correct : V - N = 12
16 Correct 107 ms 10208 KB Output is correct : V - N = 12
17 Correct 27 ms 7680 KB Output is correct : V - N = 12
18 Correct 253 ms 16080 KB Output is correct : V - N = 12
19 Correct 575 ms 26824 KB Output is correct : V - N = 12
20 Correct 662 ms 30696 KB Output is correct : V - N = 12
21 Correct 182 ms 13272 KB Output is correct : V - N = 12
22 Correct 149 ms 11736 KB Output is correct : V - N = 12
23 Correct 66 ms 8928 KB Output is correct : V - N = 12
24 Correct 15 ms 6912 KB Output is correct : V - N = 12
25 Correct 42 ms 8168 KB Output is correct : V - N = 12
26 Correct 122 ms 10968 KB Output is correct : V - N = 12
27 Correct 187 ms 13016 KB Output is correct : V - N = 12
28 Correct 165 ms 12504 KB Output is correct : V - N = 12
29 Correct 88 ms 9696 KB Output is correct : V - N = 12
30 Correct 19 ms 7536 KB Output is correct : V - N = 12
31 Correct 19 ms 7168 KB Output is correct : V - N = 12
32 Correct 19 ms 7168 KB Output is correct : V - N = 12
33 Correct 18 ms 7168 KB Output is correct : V - N = 12
34 Correct 18 ms 7168 KB Output is correct : V - N = 12
35 Correct 19 ms 7168 KB Output is correct : V - N = 12
36 Correct 688 ms 30872 KB Output is correct : V - N = 12
37 Correct 652 ms 31152 KB Output is correct : V - N = 12
38 Correct 688 ms 30672 KB Output is correct : V - N = 12
39 Correct 664 ms 30664 KB Output is correct : V - N = 12
40 Correct 664 ms 30920 KB Output is correct : V - N = 12
41 Correct 129 ms 11224 KB Output is correct : V - N = 12
42 Correct 106 ms 10208 KB Output is correct : V - N = 12
43 Correct 125 ms 10664 KB Output is correct : V - N = 12
44 Correct 20 ms 7168 KB Output is correct : V - N = 12
45 Correct 83 ms 9184 KB Output is correct : V - N = 12
46 Correct 229 ms 14800 KB Output is correct : V - N = 12
47 Correct 128 ms 10968 KB Output is correct : V - N = 12
48 Correct 305 ms 17616 KB Output is correct : V - N = 12
49 Correct 67 ms 8928 KB Output is correct : V - N = 12
50 Correct 30 ms 7936 KB Output is correct : V - N = 12
51 Correct 516 ms 25812 KB Output is correct : V - N = 12
52 Correct 20 ms 7424 KB Output is correct : V - N = 12
53 Correct 493 ms 23592 KB Output is correct : V - N = 12
54 Correct 574 ms 27336 KB Output is correct : V - N = 12
55 Correct 42 ms 8440 KB Output is correct : V - N = 12
56 Correct 348 ms 18640 KB Output is correct : V - N = 12
57 Correct 611 ms 29008 KB Output is correct : V - N = 12
58 Correct 98 ms 10208 KB Output is correct : V - N = 12
59 Correct 265 ms 15568 KB Output is correct : V - N = 12
60 Correct 657 ms 29896 KB Output is correct : V - N = 12
61 Correct 15 ms 7168 KB Output is correct : V - N = 12
62 Correct 14 ms 6912 KB Output is correct : V - N = 12
63 Correct 13 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 13 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 6760 KB Output is correct : V - N = 12
73 Runtime error 17 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Halted 0 ms 0 KB -