oj.uz

Submission #788615

# Submission time Handle Problem Language Result Execution time Memory
788615 2023-07-20T12:17:00 Z WLZ ICC (CEOI16_icc) C++17
100 / 100
 99 ms 552 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
 
class dsu {
  private:
    vector<int> p, rank;
  public:
    dsu(int n) {
      p.assign(n, -1);
      rank.assign(n, 0);
    }
 
    int root(int x) {
      if (p[x] == -1) {
        return x;
      }
      return (p[x] = root(p[x]));
    }
 
    int same_set(int x, int y) {
      return (root(x) == root(y));
    }
 
    void connect(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
        if (rank[x] > rank[y]) {
          p[y] = x;
        } else {
          p[x] = y;
          if (rank[x] == rank[y]) {
            rank[y]++;
          }
        }
      }
    }
};
 
pair<int, int> solve(vector<int> l, vector<int> r) {
  if ((int) l.size() == 1) {
    if ((int) r.size() == 1) return {l[0], r[0]};
    swap(l, r);
  }
  vector<int> tmp_l, tmp_r;
  for (int i = 0; i < (int) l.size(); i++) {
    if (i % 2 == 0) tmp_l.push_back(l[i]);
    else tmp_r.push_back(l[i]);
  }
  if (query((int) tmp_l.size(), (int) r.size(), tmp_l.data(), r.data())) return solve(tmp_l, r);
  else return solve(tmp_r, r);
}
 
void run(int n) {
  int m = n - 1;
  dsu g(n + 1);
  while (m--) {
    map<int, vector<int> > mp;
    for (int i = 1; i <= n; i++) mp[g.root(i)].push_back(i);
    vector< vector<int> > cc;
    for (auto &p : mp) cc.push_back(p.second);
    for (int k = 2; ; k *= 2) {
      vector<int> l, r;
      for (int i = 0; i < (int) cc.size(); i++) {
        if ((i % k) < (k / 2)) l.insert(l.end(), cc[i].begin(), cc[i].end());
        else r.insert(r.end(), cc[i].begin(), cc[i].end());        
      }
      if (query((int) l.size(), (int) r.size(), l.data(), r.data())) {
        auto ans = solve(l, r);
        g.connect(ans.first, ans.second);
        setRoad(ans.first, ans.second);
        break;
      }
    }
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 492 KB Ok! 96 queries used.
2 Correct 6 ms 496 KB Ok! 95 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 512 KB Ok! 534 queries used.
2 Correct 30 ms 488 KB Ok! 658 queries used.
3 Correct 26 ms 500 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 528 KB Ok! 1416 queries used.
2 Correct 93 ms 552 KB Ok! 1567 queries used.
3 Correct 80 ms 516 KB Ok! 1582 queries used.
4 Correct 75 ms 532 KB Ok! 1484 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 528 KB Ok! 1464 queries used.
2 Correct 77 ms 520 KB Ok! 1479 queries used.
3 Correct 99 ms 528 KB Ok! 1581 queries used.
4 Correct 89 ms 516 KB Ok! 1416 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 528 KB Ok! 1584 queries used.
2 Correct 79 ms 528 KB Ok! 1580 queries used.
3 Correct 81 ms 468 KB Ok! 1574 queries used.
4 Correct 81 ms 520 KB Ok! 1539 queries used.
5 Correct 74 ms 524 KB Ok! 1470 queries used.
6 Correct 87 ms 512 KB Ok! 1522 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 516 KB Ok! 1594 queries used.
2 Correct 99 ms 536 KB Ok! 1606 queries used.