oj.uz

Submission #218468

# Submission time Handle Problem Language Result Execution time Memory
218468 2020-04-02T07:55:07 Z extraterrestrial Airline Route Map (JOI18_airline) C++14
0 / 100
 702 ms 30984 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]);
  }
  int kek = 0;
  for (int i = 0; i < V; i++) {
    if (cnt[i] >= n + 10) {
      kek++;
    }
    mx = max(mx, make_pair(cnt[i], i));
  }
  assert(kek == 1);
  if (mx.F != n + 10) {
    exit(0);
  }
  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 6912 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 Correct 13 ms 6912 KB Output is correct
10 Correct 13 ms 6912 KB Output is correct
11 Correct 13 ms 6912 KB Output is correct
12 Correct 13 ms 6912 KB Output is correct
13 Correct 13 ms 6912 KB Output is correct
14 Correct 13 ms 6912 KB Output is correct
15 Correct 14 ms 6912 KB Output is correct
16 Correct 14 ms 6912 KB Output is correct
17 Correct 13 ms 6816 KB Output is correct
18 Correct 13 ms 6912 KB Output is correct
19 Correct 13 ms 6912 KB Output is correct
20 Correct 13 ms 6912 KB Output is correct
21 Correct 13 ms 6912 KB Output is correct
22 Correct 13 ms 6912 KB Output is correct
23 Correct 13 ms 6912 KB Output is correct
24 Correct 13 ms 6912 KB Output is correct
25 Correct 13 ms 6912 KB Output is correct
26 Correct 13 ms 6912 KB Output is correct
27 Correct 13 ms 6912 KB Output is correct
28 Runtime error 16 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 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 6912 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 Correct 13 ms 6912 KB Output is correct
10 Correct 13 ms 6912 KB Output is correct
11 Correct 13 ms 6912 KB Output is correct
12 Correct 13 ms 6912 KB Output is correct
13 Correct 13 ms 6912 KB Output is correct
14 Correct 13 ms 6912 KB Output is correct
15 Correct 14 ms 6912 KB Output is correct
16 Correct 14 ms 6912 KB Output is correct
17 Correct 13 ms 6816 KB Output is correct
18 Correct 13 ms 6912 KB Output is correct
19 Correct 13 ms 6912 KB Output is correct
20 Correct 13 ms 6912 KB Output is correct
21 Correct 13 ms 6912 KB Output is correct
22 Correct 13 ms 6912 KB Output is correct
23 Correct 13 ms 6912 KB Output is correct
24 Correct 13 ms 6912 KB Output is correct
25 Correct 13 ms 6912 KB Output is correct
26 Correct 13 ms 6912 KB Output is correct
27 Correct 13 ms 6912 KB Output is correct
28 Runtime error 16 ms 6912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 30920 KB Output is correct : V - N = 12
2 Correct 528 ms 25688 KB Output is correct : V - N = 12
3 Correct 215 ms 14164 KB Output is correct : V - N = 12
4 Correct 20 ms 7424 KB Output is correct : V - N = 12
5 Correct 137 ms 11224 KB Output is correct : V - N = 12
6 Correct 436 ms 23876 KB Output is correct : V - N = 12
7 Correct 618 ms 30600 KB Output is correct : V - N = 12
8 Correct 594 ms 28360 KB Output is correct : V - N = 12
9 Correct 301 ms 17616 KB Output is correct : V - N = 12
10 Correct 43 ms 8184 KB Output is correct : V - N = 12
11 Correct 71 ms 9080 KB Output is correct : V - N = 12
12 Correct 353 ms 18896 KB Output is correct : V - N = 12
13 Correct 624 ms 29128 KB Output is correct : V - N = 12
14 Correct 636 ms 29968 KB Output is correct : V - N = 12
15 Correct 410 ms 22868 KB Output is correct : V - N = 12
16 Correct 114 ms 10008 KB Output is correct : V - N = 12
17 Correct 26 ms 7680 KB Output is correct : V - N = 12
18 Correct 257 ms 15824 KB Output is correct : V - N = 12
19 Correct 556 ms 27048 KB Output is correct : V - N = 12
20 Correct 615 ms 30704 KB Output is correct : V - N = 12
21 Correct 185 ms 13176 KB Output is correct : V - N = 12
22 Correct 146 ms 11736 KB Output is correct : V - N = 12
23 Correct 66 ms 8928 KB Output is correct : V - N = 12
24 Correct 16 ms 6912 KB Output is correct : V - N = 12
25 Correct 40 ms 8288 KB Output is correct : V - N = 12
26 Correct 122 ms 10968 KB Output is correct : V - N = 12
27 Correct 178 ms 13528 KB Output is correct : V - N = 12
28 Correct 167 ms 12504 KB Output is correct : V - N = 12
29 Correct 94 ms 9952 KB Output is correct : V - N = 12
30 Correct 19 ms 7424 KB Output is correct : V - N = 12
31 Correct 19 ms 7168 KB Output is correct : V - N = 12
32 Correct 18 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 674 ms 30816 KB Output is correct : V - N = 12
37 Correct 671 ms 30664 KB Output is correct : V - N = 12
38 Correct 651 ms 30736 KB Output is correct : V - N = 12
39 Correct 698 ms 30656 KB Output is correct : V - N = 12
40 Correct 702 ms 30984 KB Output is correct : V - N = 12
41 Correct 130 ms 11176 KB Output is correct : V - N = 12
42 Correct 108 ms 10208 KB Output is correct : V - N = 12
43 Correct 107 ms 10808 KB Output is correct : V - N = 12
44 Correct 22 ms 7424 KB Output is correct : V - N = 12
45 Correct 82 ms 9296 KB Output is correct : V - N = 12
46 Correct 235 ms 14800 KB Output is correct : V - N = 12
47 Correct 132 ms 10984 KB Output is correct : V - N = 12
48 Correct 299 ms 17592 KB Output is correct : V - N = 12
49 Correct 73 ms 9008 KB Output is correct : V - N = 12
50 Correct 32 ms 7936 KB Output is correct : V - N = 12
51 Correct 521 ms 25836 KB Output is correct : V - N = 12
52 Correct 24 ms 7424 KB Output is correct : V - N = 12
53 Correct 419 ms 23644 KB Output is correct : V - N = 12
54 Correct 577 ms 27344 KB Output is correct : V - N = 12
55 Correct 41 ms 8184 KB Output is correct : V - N = 12
56 Correct 331 ms 18888 KB Output is correct : V - N = 12
57 Correct 619 ms 29128 KB Output is correct : V - N = 12
58 Correct 98 ms 10208 KB Output is correct : V - N = 12
59 Correct 258 ms 16336 KB Output is correct : V - N = 12
60 Correct 642 ms 30152 KB Output is correct : V - N = 12
61 Correct 14 ms 6912 KB Output is correct : V - N = 12
62 Correct 13 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 14 ms 6912 KB Output is correct : V - N = 12
73 Correct 14 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 14 ms 6912 KB Output is correct : V - N = 12
79 Correct 13 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 Correct 14 ms 6912 KB Output is correct : V - N = 12
83 Correct 14 ms 6912 KB Output is correct : V - N = 12
84 Correct 15 ms 6912 KB Output is correct : V - N = 12
85 Correct 13 ms 6912 KB Output is correct : V - N = 12
86 Correct 13 ms 6912 KB Output is correct : V - N = 12
87 Correct 13 ms 6912 KB Output is correct : V - N = 12
88 Correct 13 ms 6912 KB Output is correct : V - N = 12
89 Correct 13 ms 6912 KB Output is correct : V - N = 12
90 Correct 13 ms 6912 KB Output is correct : V - N = 12
91 Correct 13 ms 6912 KB Output is correct : V - N = 12
92 Correct 13 ms 6912 KB Output is correct : V - N = 12
93 Correct 13 ms 6656 KB Output is correct : V - N = 12
94 Correct 13 ms 6656 KB Output is correct : V - N = 12
95 Correct 14 ms 6912 KB Output is correct : V - N = 12
96 Incorrect 15 ms 6912 KB Wrong Answer [120]
97 Halted 0 ms 0 KB -