oj.uz

답안 #1093185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093185 2024-09-26T07:37:58 Z Fran CEOI16_icc (CEOI16_icc) C++17
100 / 100
 101 ms 856 KB 
#include "icc.h"

#include<bits/stdc++.h>
using namespace std;

constexpr int N = 101;

int rang[N];

vector<int> ver[N];

int qry(vector<int> a, vector<int> b) {
  return query(a.size(), b.size(), &a[0], &b[0]);
}

int find(vector<int> a, vector<int> b) {
  if(a.size() == 1) return a[0];

  int mid = a.size() / 2;
  auto lv = vector(a.begin(), a.begin()+mid), rv = vector(a.begin()+mid, a.end());
  return qry(lv, b) ? find(lv, b) : find(rv, b);
}

void run(int n) {
  iota(rang, rang+n+1, 0);
  for(int i = 1; i <= n; ++i) ver[i].push_back(i);
  for(int e = 0; e < n - 1; ++e) {
    vector<int> root;
    for(int i = 1; i <= n; ++i) if(rang[i] == i) root.push_back(i);
    int roots = root.size();
    int x = 0, k = -1;
    for(int i = 0; (1 << i) < roots; ++i) {
      vector<int> a, b;
      for(int j = 0; j < roots; ++j) {
        auto& v = (j >> i) & 1 ? a : b;
        v.insert(v.end(), ver[root[j]].begin(), ver[root[j]].end());
      }
      if(qry(a, b)) {
        x ^= (1 << i);
        k = i;
      }
    }
    int y = 0;
    for(int i = 0; (1 << i) < roots; ++i) {
      if(i == k) continue;
      vector<int> a, b;
      for(int j = 0; j < roots; ++j) {
        auto& v = j & (1 << i | 1 << k) ? a : b;
        v.insert(v.end(), ver[root[j]].begin(), ver[root[j]].end());
      }
      if(!qry(a, b)) y ^= (1 << i);
    }
    x ^= y;

    int u = find(ver[root[x]], ver[root[y]]);
    int v = find(ver[root[y]], ver[root[x]]);
    setRoad(u, v);
    for(auto& x : ver[rang[v]]) {
      rang[x] = rang[u];
      ver[rang[u]].push_back(x);
    }
  }
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 600 KB Ok! 117 queries used.
2 Correct 5 ms 604 KB Ok! 116 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 604 KB Ok! 650 queries used.
2 Correct 26 ms 640 KB Ok! 551 queries used.
3 Correct 26 ms 600 KB Ok! 591 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 612 KB Ok! 1573 queries used.
2 Correct 78 ms 632 KB Ok! 1372 queries used.
3 Correct 91 ms 856 KB Ok! 1613 queries used.
4 Correct 101 ms 604 KB Ok! 1497 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 648 KB Ok! 1564 queries used.
2 Correct 87 ms 608 KB Ok! 1543 queries used.
3 Correct 84 ms 632 KB Ok! 1488 queries used.
4 Correct 89 ms 640 KB Ok! 1608 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 636 KB Ok! 1414 queries used.
2 Correct 84 ms 604 KB Ok! 1433 queries used.
3 Correct 85 ms 600 KB Ok! 1424 queries used.
4 Correct 81 ms 444 KB Ok! 1452 queries used.
5 Correct 91 ms 604 KB Ok! 1587 queries used.
6 Correct 87 ms 600 KB Ok! 1575 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 636 KB Ok! 1448 queries used.
2 Correct 79 ms 604 KB Ok! 1420 queries used.