oj.uz

Submission #116676

# Submission time Handle Problem Language Result Execution time Memory
116676 2019-06-13T14:08:37 Z IOrtroiii ICC (CEOI16_icc) C++14
90 / 100
 133 ms 636 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int N = 105;

int qa[N], qb[N];

int query(vector<int> a, vector<int> b) {
   int sza = a.size(), szb = b.size();
   for (int i = 0; i < sza; ++i) {
      qa[i] = a[i];
   }
   for (int i = 0; i < szb; ++i) {
      qb[i] = b[i];
   }
   return query(sza, szb, qa, qb);
}

int fnd(int l, int r, vector<int> &from, vector<int> &to) {
   if (l == r) { return from[l]; }
   int md = (l + r) >> 1;
   vector<int> ll;
   for (int i = l; i <= md; ++i) {
      ll.push_back(from[i]);
   }
   if (query(ll, to)) {
      return fnd(l, md, from, to);
   } else {
      return fnd(md + 1, r, from, to);
   }
}

int p[N];
vector<int> comp[N];

int getp(int u) {
   if (p[u] == u) {
      return u;
   } else {
      return p[u] = getp(p[u]);
   }
}

void mrg(int u, int v) {
   u = getp(u), v = getp(v);
   if (comp[u].size() < comp[v].size()) {
      swap(u, v);
   }
   p[v] = u;
   for (int w : comp[v]) {
      comp[u].push_back(w);
   }
}

void modify(vector<int> l, vector<int> r) {
   int u = fnd(0, l.size() - 1, l, r);
   int v = fnd(0, r.size() - 1, r, l);
   mrg(u, v);
   setRoad(u, v);
}

int n;

void solve() {
   vector<int> roots;
   for (int i = 1; i <= n; ++i) {
      if (p[i] == i) {
         roots.push_back(i);
      }
   }
   for (int i = 0; (1 << i) < roots.size(); ++i) {
      vector<int> l, r;
      for (int j = 0; j < roots.size(); ++j) {
         if (j & (1 << i)) {
            for (int v : comp[roots[j]]) {
               l.push_back(v);
            }
         } else {
            for (int v : comp[roots[j]]) {
               r.push_back(v);
            }
         }
      }
      if (l.empty() || r.empty()) {
         continue;
      }
      if (query(l, r)) {
         modify(l, r);
         return;
      }
   }
}

void run(int n) {
   ::n = n;
   for (int i = 1; i <= n; ++i) {
      p[i] = i;
      comp[i].push_back(i);
   }
   for (int i = 0; i < n - 1; ++i) {
      solve();
   }
}

Compilation message

icc.cpp: In function 'void solve()':
icc.cpp:72:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; (1 << i) < roots.size(); ++i) {
                    ~~~~~~~~~^~~~~~~~~~~~~~
icc.cpp:74:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < roots.size(); ++j) {
                       ~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Ok! 99 queries used.
2 Correct 7 ms 512 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 512 KB Ok! 535 queries used.
2 Correct 43 ms 512 KB Ok! 659 queries used.
3 Correct 40 ms 512 KB Ok! 658 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 512 KB Ok! 1424 queries used.
2 Correct 119 ms 600 KB Ok! 1612 queries used.
3 Correct 125 ms 564 KB Ok! 1655 queries used.
4 Correct 118 ms 512 KB Ok! 1504 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 512 KB Ok! 1596 queries used.
2 Correct 130 ms 512 KB Ok! 1472 queries used.
3 Correct 126 ms 564 KB Ok! 1636 queries used.
4 Correct 123 ms 632 KB Ok! 1519 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 512 KB Ok! 1629 queries used.
2 Correct 118 ms 572 KB Ok! 1611 queries used.
3 Correct 125 ms 512 KB Ok! 1646 queries used.
4 Correct 125 ms 636 KB Ok! 1653 queries used.
5 Correct 133 ms 512 KB Ok! 1486 queries used.
6 Correct 132 ms 576 KB Ok! 1555 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 600 KB Too many queries! 1635 out of 1625
2 Halted 0 ms 0 KB -