Submission #218474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218474	2020-04-02T07:57:40 Z	extraterrestrial	Airline Route Map (JOI18_airline)	C++14	0 / 100	731 ms	31160 KB

Alice
Bob

#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));
  }
  if (SZ(path) < 10) {
    exit(0);
  }
  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	6864 KB	Output is correct
4	Correct	14 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	13 ms	6912 KB	Output is correct
16	Correct	13 ms	6912 KB	Output is correct
17	Correct	13 ms	6912 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	14 ms	6912 KB	Output is correct
28	Correct	13 ms	6912 KB	Output is correct
29	Correct	13 ms	6912 KB	Output is correct
30	Correct	13 ms	6912 KB	Output is correct
31	Correct	13 ms	6912 KB	Output is correct
32	Correct	13 ms	6912 KB	Output is correct
33	Correct	13 ms	6912 KB	Output is correct
34	Correct	13 ms	6912 KB	Output is correct
35	Correct	13 ms	6912 KB	Output is correct
36	Correct	13 ms	6912 KB	Output is correct
37	Correct	13 ms	6912 KB	Output is correct
38	Correct	13 ms	6912 KB	Output is correct
39	Correct	13 ms	6912 KB	Output is correct
40	Incorrect	13 ms	6912 KB	Unexpected end of file - token expected
41	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	6864 KB	Output is correct
4	Correct	14 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	13 ms	6912 KB	Output is correct
16	Correct	13 ms	6912 KB	Output is correct
17	Correct	13 ms	6912 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	14 ms	6912 KB	Output is correct
28	Correct	13 ms	6912 KB	Output is correct
29	Correct	13 ms	6912 KB	Output is correct
30	Correct	13 ms	6912 KB	Output is correct
31	Correct	13 ms	6912 KB	Output is correct
32	Correct	13 ms	6912 KB	Output is correct
33	Correct	13 ms	6912 KB	Output is correct
34	Correct	13 ms	6912 KB	Output is correct
35	Correct	13 ms	6912 KB	Output is correct
36	Correct	13 ms	6912 KB	Output is correct
37	Correct	13 ms	6912 KB	Output is correct
38	Correct	13 ms	6912 KB	Output is correct
39	Correct	13 ms	6912 KB	Output is correct
40	Incorrect	13 ms	6912 KB	Unexpected end of file - token expected
41	Halted	0 ms	0 KB	-

Subtask #3
0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	679 ms	30616 KB	Output is correct : V - N = 12
2	Correct	527 ms	26044 KB	Output is correct : V - N = 12
3	Correct	223 ms	14036 KB	Output is correct : V - N = 12
4	Correct	20 ms	7424 KB	Output is correct : V - N = 12
5	Correct	122 ms	11488 KB	Output is correct : V - N = 12
6	Correct	434 ms	24144 KB	Output is correct : V - N = 12
7	Correct	680 ms	30448 KB	Output is correct : V - N = 12
8	Correct	580 ms	27848 KB	Output is correct : V - N = 12
9	Correct	282 ms	17472 KB	Output is correct : V - N = 12
10	Correct	44 ms	8184 KB	Output is correct : V - N = 12
11	Correct	71 ms	9184 KB	Output is correct : V - N = 12
12	Correct	360 ms	18896 KB	Output is correct : V - N = 12
13	Correct	642 ms	28880 KB	Output is correct : V - N = 12
14	Correct	731 ms	29912 KB	Output is correct : V - N = 12
15	Correct	401 ms	22672 KB	Output is correct : V - N = 12
16	Correct	101 ms	10160 KB	Output is correct : V - N = 12
17	Correct	36 ms	7928 KB	Output is correct : V - N = 12
18	Correct	252 ms	15784 KB	Output is correct : V - N = 12
19	Correct	558 ms	26780 KB	Output is correct : V - N = 12
20	Correct	665 ms	30632 KB	Output is correct : V - N = 12
21	Correct	195 ms	13272 KB	Output is correct : V - N = 12
22	Correct	154 ms	11992 KB	Output is correct : V - N = 12
23	Correct	55 ms	8944 KB	Output is correct : V - N = 12
24	Correct	17 ms	7168 KB	Output is correct : V - N = 12
25	Correct	48 ms	8184 KB	Output is correct : V - N = 12
26	Correct	125 ms	10968 KB	Output is correct : V - N = 12
27	Correct	188 ms	13272 KB	Output is correct : V - N = 12
28	Correct	161 ms	12504 KB	Output is correct : V - N = 12
29	Correct	78 ms	9696 KB	Output is correct : V - N = 12
30	Correct	20 ms	7424 KB	Output is correct : V - N = 12
31	Correct	20 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	18 ms	7168 KB	Output is correct : V - N = 12
35	Correct	19 ms	7168 KB	Output is correct : V - N = 12
36	Correct	663 ms	31160 KB	Output is correct : V - N = 12
37	Correct	692 ms	30696 KB	Output is correct : V - N = 12
38	Correct	637 ms	30600 KB	Output is correct : V - N = 12
39	Correct	662 ms	30952 KB	Output is correct : V - N = 12
40	Correct	660 ms	30664 KB	Output is correct : V - N = 12
41	Correct	126 ms	11224 KB	Output is correct : V - N = 12
42	Correct	111 ms	10208 KB	Output is correct : V - N = 12
43	Correct	127 ms	10968 KB	Output is correct : V - N = 12
44	Correct	20 ms	7168 KB	Output is correct : V - N = 12
45	Correct	76 ms	9184 KB	Output is correct : V - N = 12
46	Correct	253 ms	14800 KB	Output is correct : V - N = 12
47	Correct	130 ms	10968 KB	Output is correct : V - N = 12
48	Correct	315 ms	17616 KB	Output is correct : V - N = 12
49	Correct	60 ms	8928 KB	Output is correct : V - N = 12
50	Correct	32 ms	7680 KB	Output is correct : V - N = 12
51	Correct	526 ms	25812 KB	Output is correct : V - N = 12
52	Correct	23 ms	7424 KB	Output is correct : V - N = 12
53	Correct	401 ms	23664 KB	Output is correct : V - N = 12
54	Correct	583 ms	27336 KB	Output is correct : V - N = 12
55	Correct	40 ms	8184 KB	Output is correct : V - N = 12
56	Correct	309 ms	18896 KB	Output is correct : V - N = 12
57	Correct	632 ms	29128 KB	Output is correct : V - N = 12
58	Correct	93 ms	9952 KB	Output is correct : V - N = 12
59	Correct	229 ms	15824 KB	Output is correct : V - N = 12
60	Correct	640 ms	29896 KB	Output is correct : V - N = 12
61	Correct	15 ms	6912 KB	Output is correct : V - N = 12
62	Correct	14 ms	6720 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	14 ms	6912 KB	Output is correct : V - N = 12
66	Correct	14 ms	6912 KB	Output is correct : V - N = 12
67	Correct	13 ms	6912 KB	Output is correct : V - N = 12
68	Correct	15 ms	6912 KB	Output is correct : V - N = 12
69	Correct	14 ms	6912 KB	Output is correct : V - N = 12
70	Correct	13 ms	6912 KB	Output is correct : V - N = 12
71	Correct	15 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	15 ms	6912 KB	Output is correct : V - N = 12
75	Correct	15 ms	6912 KB	Output is correct : V - N = 12
76	Correct	14 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	14 ms	6912 KB	Output is correct : V - N = 12
80	Correct	14 ms	6912 KB	Output is correct : V - N = 12
81	Correct	14 ms	6912 KB	Output is correct : V - N = 12
82	Correct	14 ms	6912 KB	Output is correct : V - N = 12
83	Correct	13 ms	6912 KB	Output is correct : V - N = 12
84	Correct	14 ms	6912 KB	Output is correct : V - N = 12
85	Correct	14 ms	6912 KB	Output is correct : V - N = 12
86	Correct	14 ms	6912 KB	Output is correct : V - N = 12
87	Correct	14 ms	6912 KB	Output is correct : V - N = 12
88	Correct	13 ms	6912 KB	Output is correct : V - N = 12
89	Correct	14 ms	6912 KB	Output is correct : V - N = 12
90	Correct	13 ms	6864 KB	Output is correct : V - N = 12
91	Correct	13 ms	6656 KB	Output is correct : V - N = 12
92	Correct	13 ms	6912 KB	Output is correct : V - N = 12
93	Correct	15 ms	6912 KB	Output is correct : V - N = 12
94	Correct	14 ms	6656 KB	Output is correct : V - N = 12
95	Correct	14 ms	6912 KB	Output is correct : V - N = 12
96	Correct	15 ms	6912 KB	Output is correct : V - N = 12
97	Correct	16 ms	6912 KB	Output is correct : V - N = 12
98	Correct	14 ms	6912 KB	Output is correct : V - N = 12
99	Correct	15 ms	6912 KB	Output is correct : V - N = 12
100	Correct	13 ms	6912 KB	Output is correct : V - N = 12
101	Correct	13 ms	6912 KB	Output is correct : V - N = 12
102	Correct	14 ms	6912 KB	Output is correct : V - N = 12
103	Correct	13 ms	6912 KB	Output is correct : V - N = 12
104	Correct	13 ms	6912 KB	Output is correct : V - N = 12
105	Correct	13 ms	6912 KB	Output is correct : V - N = 12
106	Correct	13 ms	6912 KB	Output is correct : V - N = 12
107	Correct	15 ms	6912 KB	Output is correct : V - N = 12
108	Correct	15 ms	6912 KB	Output is correct : V - N = 12
109	Correct	13 ms	6912 KB	Output is correct : V - N = 12
110	Correct	14 ms	6912 KB	Output is correct : V - N = 12
111	Correct	13 ms	6912 KB	Output is correct : V - N = 12
112	Correct	13 ms	6912 KB	Output is correct : V - N = 12
113	Correct	13 ms	6912 KB	Output is correct : V - N = 12
114	Correct	13 ms	6912 KB	Output is correct : V - N = 12
115	Correct	13 ms	6912 KB	Output is correct : V - N = 12
116	Correct	13 ms	6912 KB	Output is correct : V - N = 12
117	Correct	13 ms	6912 KB	Output is correct : V - N = 12
118	Correct	13 ms	6912 KB	Output is correct : V - N = 12
119	Correct	13 ms	6912 KB	Output is correct : V - N = 12
120	Correct	13 ms	6912 KB	Output is correct : V - N = 12
121	Correct	13 ms	6912 KB	Output is correct : V - N = 12
122	Correct	13 ms	6912 KB	Output is correct : V - N = 12
123	Correct	13 ms	6912 KB	Output is correct : V - N = 12
124	Correct	13 ms	6912 KB	Output is correct : V - N = 12
125	Correct	13 ms	6912 KB	Output is correct : V - N = 12
126	Correct	13 ms	6912 KB	Output is correct : V - N = 12
127	Correct	13 ms	6912 KB	Output is correct : V - N = 12
128	Correct	15 ms	6912 KB	Output is correct : V - N = 12
129	Correct	13 ms	6912 KB	Output is correct : V - N = 12
130	Incorrect	13 ms	6656 KB	Unexpected end of file - token expected
131	Halted	0 ms	0 KB	-

Submission #218474

Compilation message

Subtask #1 0 / 22.0

Subtask #2 0 / 15.0

Subtask #3 0 / 63.0

Subtask #1
0 / 22.0

Subtask #2
0 / 15.0

Subtask #3
0 / 63.0