oj.uz

Submission #52053

# Submission time Handle Problem Language Result Execution time Memory
52053 2018-06-23T11:22:37 Z someone_aa ICC (CEOI16_icc) C++17
90 / 100
 161 ms 852 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int maxn = 110;
int parent[maxn];

vector<int>comps[maxn];

/*bool query(int a, int b, int aa[], int bb[]) {
    for(int i=0;i<a;i++) {
        cout<<aa[i]<<" ";
    } cout<<"\n";
    for(int i=0;i<b;i++) {
        cout<<bb[i]<<" ";
    } cout<<"\n";

    bool answ;
    cin>>answ;
    return answ;
}

void setRoad(int x, int y) {
    cout<<"Road: "<<x<<" "<<y<<"\n";
}*/

int uroot(int x) {
    while(x != parent[x]) x = parent[x];
    return x;
}

void unite(int x, int y) {
    x = uroot(x);
    y = uroot(y);

    if(x==y) return;
    for(int i:comps[x]) {
        comps[y].push_back(i);
    }
    parent[x] = y;
}

bool qq(set<int>a, set<int> b) {
    int aa[a.size()], bb[b.size()];
    int br = 0;
    for(int i:a) aa[br++] = i;
    br = 0;
    for(int i:b) bb[br++] = i;
    return query(a.size(), b.size(), aa, bb);
}

int bin(set<int>a, set<int>b) {
    if(b.size() == 1) {
        return (*(b.begin()));
    }
    set<int>x;
    int br = 0;
    int li = 0, ri = b.size() - 1;

    vector<int>v;
    for(int i:b) v.push_back(i);

    while(li < ri) {
        int mid = (li+ri)/2;
        for(int i=li;i<=mid;i++) {
            x.insert(v[i]);
        }
        if(qq(a, x)) ri = mid;
        else li = mid + 1;
        x.clear();
    }
    return v[li];
}

void run(int n) {
    set<int>c;

    for(int i=1;i<=n;i++) {
        parent[i] = i;
        comps[i].push_back(i);
    }

    for(int edges=1;edges<n;edges++) {
        for(int i=1;i<=n;i++) {
            c.insert(uroot(i));
        }

        bool found = false;
        for(int i=0;i<=6;i++) {
            if(!found) {
                set<int>a, b;
                for(int j:c) {
                    if(j&(1<<i)) for(int k:comps[j]) a.insert(k);
                    else for(int k:comps[j]) b.insert(k);
                }
                if(a.size() > 0 && b.size() > 0) {
                    if(qq(a, b)) {
                        int x = bin(a, b);
                        int y = bin(b, a);
                        setRoad(x, y);
                        unite(x, y);
                        found = true;
                    }
                }
            }
        }
        c.clear();
    }
}

/*int main() {
    run(4);
    return 0;
}*/

Compilation message

icc.cpp: In function 'int bin(std::set<int>, std::set<int>)':
icc.cpp:57:9: warning: unused variable 'br' [-Wunused-variable]
     int br = 0;
         ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 101 queries used.
2 Correct 9 ms 660 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 660 KB Ok! 544 queries used.
2 Correct 54 ms 660 KB Ok! 661 queries used.
3 Correct 51 ms 712 KB Ok! 655 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 712 KB Ok! 1356 queries used.
2 Correct 161 ms 712 KB Ok! 1638 queries used.
3 Correct 129 ms 852 KB Ok! 1329 queries used.
4 Correct 144 ms 852 KB Ok! 1480 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 852 KB Ok! 1331 queries used.
2 Correct 139 ms 852 KB Ok! 1432 queries used.
3 Correct 155 ms 852 KB Ok! 1578 queries used.
4 Correct 138 ms 852 KB Ok! 1331 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 852 KB Ok! 1567 queries used.
2 Correct 154 ms 852 KB Ok! 1566 queries used.
3 Correct 157 ms 852 KB Ok! 1600 queries used.
4 Correct 149 ms 852 KB Ok! 1536 queries used.
5 Correct 140 ms 852 KB Ok! 1420 queries used.
6 Correct 156 ms 852 KB Ok! 1589 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 852 KB Ok! 1577 queries used.
2 Incorrect 159 ms 852 KB Too many queries! 1629 out of 1625