Submission #788615

#	Time	Username	Problem	Language	Result	Execution time	Memory
788615		WLZ	ICC (CEOI16_icc)	C++17	100 / 100	99 ms	552 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10