oj.uz

답안 #218476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218476 2020-04-02T07:58:53 Z extraterrestrial 항공 노선도 (JOI18_airline) C++14
0 / 100
 701 ms 31176 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);
  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));
  }
  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

# 결과 실행 시간 메모리 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 6760 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 6656 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 14 ms 6912 KB Output is correct
18 Correct 13 ms 6656 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 15 ms 6912 KB Output is correct
27 Correct 13 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 6656 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 7168 KB Output is correct
37 Correct 13 ms 6912 KB Output is correct
38 Correct 13 ms 6912 KB Output is correct
39 Incorrect 13 ms 6912 KB Unexpected end of file - token expected
40 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 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 6760 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 6656 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 14 ms 6912 KB Output is correct
18 Correct 13 ms 6656 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 15 ms 6912 KB Output is correct
27 Correct 13 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 6656 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 7168 KB Output is correct
37 Correct 13 ms 6912 KB Output is correct
38 Correct 13 ms 6912 KB Output is correct
39 Incorrect 13 ms 6912 KB Unexpected end of file - token expected
40 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 673 ms 30880 KB Output is correct : V - N = 12
2 Correct 528 ms 25804 KB Output is correct : V - N = 12
3 Correct 209 ms 14144 KB Output is correct : V - N = 12
4 Correct 20 ms 7536 KB Output is correct : V - N = 12
5 Correct 131 ms 11224 KB Output is correct : V - N = 12
6 Correct 454 ms 23904 KB Output is correct : V - N = 12
7 Correct 679 ms 30176 KB Output is correct : V - N = 12
8 Correct 608 ms 28072 KB Output is correct : V - N = 12
9 Correct 305 ms 17360 KB Output is correct : V - N = 12
10 Correct 45 ms 8440 KB Output is correct : V - N = 12
11 Correct 74 ms 9184 KB Output is correct : V - N = 12
12 Correct 351 ms 18896 KB Output is correct : V - N = 12
13 Correct 636 ms 29232 KB Output is correct : V - N = 12
14 Correct 642 ms 29640 KB Output is correct : V - N = 12
15 Correct 401 ms 22604 KB Output is correct : V - N = 12
16 Correct 98 ms 9952 KB Output is correct : V - N = 12
17 Correct 27 ms 7680 KB Output is correct : V - N = 12
18 Correct 245 ms 15800 KB Output is correct : V - N = 12
19 Correct 562 ms 26892 KB Output is correct : V - N = 12
20 Correct 665 ms 30568 KB Output is correct : V - N = 12
21 Correct 181 ms 13224 KB Output is correct : V - N = 12
22 Correct 154 ms 11736 KB Output is correct : V - N = 12
23 Correct 60 ms 9184 KB Output is correct : V - N = 12
24 Correct 17 ms 7168 KB Output is correct : V - N = 12
25 Correct 37 ms 8184 KB Output is correct : V - N = 12
26 Correct 126 ms 11080 KB Output is correct : V - N = 12
27 Correct 174 ms 13248 KB Output is correct : V - N = 12
28 Correct 169 ms 12456 KB Output is correct : V - N = 12
29 Correct 82 ms 9952 KB Output is correct : V - N = 12
30 Correct 19 ms 7536 KB Output is correct : V - N = 12
31 Correct 19 ms 7264 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 19 ms 7168 KB Output is correct : V - N = 12
35 Correct 18 ms 7168 KB Output is correct : V - N = 12
36 Correct 649 ms 31176 KB Output is correct : V - N = 12
37 Correct 684 ms 30664 KB Output is correct : V - N = 12
38 Correct 667 ms 30664 KB Output is correct : V - N = 12
39 Correct 701 ms 30592 KB Output is correct : V - N = 12
40 Correct 665 ms 30840 KB Output is correct : V - N = 12
41 Correct 127 ms 11224 KB Output is correct : V - N = 12
42 Correct 99 ms 10184 KB Output is correct : V - N = 12
43 Correct 122 ms 10712 KB Output is correct : V - N = 12
44 Correct 19 ms 7424 KB Output is correct : V - N = 12
45 Correct 75 ms 9184 KB Output is correct : V - N = 12
46 Correct 225 ms 15312 KB Output is correct : V - N = 12
47 Correct 126 ms 11224 KB Output is correct : V - N = 12
48 Correct 303 ms 17616 KB Output is correct : V - N = 12
49 Correct 70 ms 8928 KB Output is correct : V - N = 12
50 Correct 27 ms 7680 KB Output is correct : V - N = 12
51 Correct 514 ms 25812 KB Output is correct : V - N = 12
52 Correct 20 ms 7536 KB Output is correct : V - N = 12
53 Correct 426 ms 23500 KB Output is correct : V - N = 12
54 Correct 554 ms 27400 KB Output is correct : V - N = 12
55 Correct 40 ms 8184 KB Output is correct : V - N = 12
56 Correct 336 ms 18608 KB Output is correct : V - N = 12
57 Correct 678 ms 29232 KB Output is correct : V - N = 12
58 Correct 95 ms 9960 KB Output is correct : V - N = 12
59 Correct 254 ms 15664 KB Output is correct : V - N = 12
60 Correct 650 ms 29848 KB Output is correct : V - N = 12
61 Correct 13 ms 6912 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 14 ms 6752 KB Output is correct : V - N = 12
72 Correct 13 ms 6912 KB Output is correct : V - N = 12
73 Incorrect 13 ms 6912 KB Unexpected end of file - token expected
74 Halted 0 ms 0 KB -