Submission #605646

#	Time	Username	Problem	Language	Result	Execution time	Memory
605646		SlavicG	ICC (CEOI16_icc)	C++17	100 / 100	137 ms	616 KiB

icc

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

/*
int query(int a, int b, int* aa, int* bb) {

}
*/

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int query(vector<int> a, vector<int> b) {
    int aa[(int)a.size()], bb[(int)b.size()];
    for(int i = 0; i < (int)a.size(); ++i) aa[i] = a[i];
    for(int i = 0; i < (int)b.size(); ++i) bb[i] = b[i];
    return query(a.size(), b.size(), aa, bb);
}
struct dsu {
    vector<int> p, s;
    dsu(int n) {
        p.resize(n);
        s.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int get(int a) {return p[a] = (p[a] == a ? a : get(p[a]));}
    int sz(int a) {return s[get(a)];}
    void uni(int a, int b) {
        a = get(a);
        b = get(b);
        if(s[a] > s[b]) swap(a, b);
        p[a] = b;
        s[b] += s[a];
    }
};

int ask(vector<int> a, vector<int> b) {
    int l = 0, r = (int)a.size();
    while(l < r) {
        int mid = l + r >> 1;
        vector<int> paiu;
        for(int j = 0; j <= mid; ++j) paiu.push_back(a[j]);
        if(query(paiu, b)) {
            r = mid;
        } else l = mid + 1;
    }
    return a[r];
}

void run(int n) {
    dsu d(n + 5);
    for(int times = 0; times < n - 1; ++times) {
        int st = -1;
        vector<int> v;
        for(int i = 1; i <= n; ++i) v.push_back(d.get(i));
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        vector<int> A, B;
        vector<int> bits;
        vector<int> paiu;
        for(int bit = 0; (1 << bit) < (int)v.size(); ++bit) {
            vector<int> c1, c2;
            for(int i = 1; i <= n; ++i) {
                if((lower_bound(v.begin(), v.end(), d.get(i)) - v.begin()) & (1 << bit)) c1.push_back(i);
                else c2.push_back(i);
            }
            if(c1.empty() || c2.empty()) continue;
            if(query(c1, c2)) {
                A = c1, B = c2;
                break;
            }
        }
        assert(A.size() > 0 && B.size() > 0);
        vector<pair<int, int>> aa;
        for(auto x: A) aa.push_back({d.sz(x), x});
        sort(aa.rbegin(), aa.rend());
        A.clear();
        for(auto x: aa) A.push_back(x.second);
        aa.clear();
        for(auto x: B) aa.push_back({d.sz(x), x});
        sort(aa.rbegin(), aa.rend());
        B.clear();
        for(auto x: aa) B.push_back(x.second);

        int ansA = ask(A, B);
        int ansB = ask(B, A);
        d.uni(ansA, ansB);
        setRoad(ansA, ansB);
    }
}

/*
int main() {
    int n; cin >> n;
    run(n);
}
*/

Compilation message (stderr)

icc.cpp: In function 'int ask(std::vector<int>, std::vector<int>)':
icc.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = l + r >> 1;
      |                   ~~^~~
icc.cpp: In function 'void run(int)':
icc.cpp:53:13: warning: unused variable 'st' [-Wunused-variable]
   53 |         int st = -1;
      |             ^~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10