oj.uz

Submission #307268

# Submission time Handle Problem Language Result Execution time Memory
307268 2020-09-27T13:42:20 Z jungsnow ICC (CEOI16_icc) C++14
100 / 100
 173 ms 632 KB 
#include<bits/stdc++.h>
#include "icc.h"
#define bug(x) cerr<<#x<<" = "<<x<<endl

using namespace std;

const int N = 105;

//bool query(int n, int m, int a[], int b[]) {
//    bool ok;
//    cout<<"ask\n";
//    cout<<"a ";
//    for (int i = 0; i < n; ++i)
//        cout<<a[i]<<' ';
//    cout<<endl;
//    cout<<"b ";
//    for (int i = 0; i < m; ++i)
//        cout<<b[i]<< ' ';
//    cout<<endl;
//    cin >> ok;
//    return ok;
//}
//
//void setRoad(int u, int v) {
//    cout<<"is "<<u<<' '<<v<<endl<<endl;
//}

int par[N];
vector<int> vec[N];

int find(int u) {
    return (par[u] == u) ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
    u = find(u), v = find(v);
    if (vec[u].size() > vec[v].size()) swap(u, v);
    for (auto i : vec[u]) vec[v].push_back(i);
    par[u] = v, vec[u].clear();
}

bool query(vector<int> a, vector<int> b) {
    int sza = a.size(), szb = b.size();
    if (sza <= 0 || szb <= 0) return 0;
    int A[N], B[N];
    for (int i = 0; i < sza; ++i) A[i] = a[i];
    for (int i = 0; i < szb; ++i) B[i] = b[i];
    return query(sza, szb, A, B);
}

void find(int l, int r, vector<int> &go, vector<int>& to) {
    if (l == r) {
        int tmp = go[l]; go.clear(); go.push_back(tmp); return;
    }
    int mid = (l + r) >> 1;
    vector<int> a, b; b = to;
    for (int i = l; i <= mid; ++i) a.push_back(go[i]);
    if (query(a, b)) find(l, mid, go, to);
    else find(mid + 1, r, go, to);
}

void cal(vector<int> vx, vector<int> vy) {
    if (vx.empty() || vy.empty()) return;
    find(0, vx.size() - 1, vx, vy);
    find(0, vy.size() - 1, vy, vx);
    setRoad(vx[0], vy[0]), join(vx[0], vy[0]);
}

void run(int n) {
    for (int i = 1; i <= n; ++i) par[i] = i, vec[i].push_back(i);
    for (int t = 1; t < n; ++t) {
        vector<int> go;
        for (int i = 1; i <= n; ++i)
            if (find(i) == i) go.push_back(i);
//        cout<<"GO = "<<endl;
//        for (int x : go) cout<<x<<' ';
//        cout<<endl;
        int sz = go.size(), m = 0, id, A = 0, B = 0; /// m = A xor B
        for (int i = 0; (1 << i) < sz; ++i) {
            vector<int> a, b;
            for (int j = 0; j < sz; ++j) {
                if ((j >> i) & 1) {
                    for (int k : vec[go[j]]) a.push_back(k);
                } else {
                    for (int k : vec[go[j]]) b.push_back(k);
                }
            }
            if (query(a, b)) m |= (1 << i), id = i;
        }
        B |= (1 << id);
        for (int i = 0; (1 << i) < sz; ++i) if (i != id) {
            if ((m >> i) & 1) {
                vector<int> a, b;
                for (int j = 0; j < sz; ++j) {
                    if ( (((j >> i) & 1) == 0) && (((j >> id) & 1) == 0) ) {
                        for (int k : vec[go[j]]) a.push_back(k);
                    }
                    if ( (((j >> i) & 1) == 1) && (((j >> id) & 1) == 1) ) {
                        for (int k : vec[go[j]]) b.push_back(k);
                    }
                }
                if (query(a, b)) {
                    B |= (1 << i);
                } else
                    A |= (1 << i);
            } else {
                vector<int> a, b;
                for (int j = 0; j < sz; ++j) if (((j >> i) & 1) == 0) {
                    if (j >> id & 1) {
                        for (int k : vec[go[j]]) a.push_back(k);
                    } else {
                        for (int k : vec[go[j]]) b.push_back(k);
                    }
                }
                if (query(a, b) == 0) {
                    A |= (1 << i);
                    B |= (1 << i);
                }
            }
        }
        cal(vec[go[A]], vec[go[B]]);
    }
}
//
//int main() {
//    int n; cin >> n;
//    run(n);
//}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:90:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |         B |= (1 << id);
      |              ~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Ok! 114 queries used.
2 Correct 8 ms 512 KB Ok! 112 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 512 KB Ok! 638 queries used.
2 Correct 44 ms 512 KB Ok! 540 queries used.
3 Correct 45 ms 512 KB Ok! 577 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 512 KB Ok! 1572 queries used.
2 Correct 143 ms 512 KB Ok! 1337 queries used.
3 Correct 161 ms 632 KB Ok! 1609 queries used.
4 Correct 165 ms 512 KB Ok! 1519 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 572 KB Ok! 1541 queries used.
2 Correct 155 ms 512 KB Ok! 1488 queries used.
3 Correct 149 ms 544 KB Ok! 1466 queries used.
4 Correct 160 ms 632 KB Ok! 1591 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 568 KB Ok! 1366 queries used.
2 Correct 145 ms 512 KB Ok! 1389 queries used.
3 Correct 173 ms 564 KB Ok! 1402 queries used.
4 Correct 151 ms 512 KB Ok! 1440 queries used.
5 Correct 157 ms 512 KB Ok! 1592 queries used.
6 Correct 155 ms 572 KB Ok! 1593 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 568 KB Ok! 1429 queries used.
2 Correct 145 ms 512 KB Ok! 1375 queries used.