oj.uz

Submission #341599

# Submission time Handle Problem Language Result Execution time Memory
341599 2020-12-30T07:23:06 Z phathnv ICC (CEOI16_icc) C++11
0 / 100
 87 ms 748 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

typedef long long ll;

const int N = 101;

int n, root[N];

bool myQuery(vector <int> &a, vector <int> &b){
    if (a.empty() || b.empty())
        return 0;
    return query(a.size(), b.size(), a.data(), b.data());
}

void mySetRoad(int u, int v){
    setRoad(u, v);
    if (root[u] > root[v])
        swap(u, v);
    for(int i = 1; i <= n; i++)
        if (root[i] == root[v])
            root[i] = root[u];
}

pair <int, int> findEdge(){
    vector <int> a, b;
    for(int i = 0; i <= 6; i++){
        a.clear();
        b.clear();
        for(int u = 1; u <= n; u++)
            if (root[u] & (1 << i))
                a.push_back(u);
            else
                b.push_back(u);
        if (myQuery(a, b))
            break;
    }

    for(int t = 0; t < 2; t++){
        int l = 0, r = a.size() - 1;
        while (l < r){
            int mid = (l + r) >> 1;
            vector <int> tmp;
            for(int i = l; i <= mid; i++)
                tmp.push_back(a[i]);
            if (myQuery(tmp, b))
                r = mid;
            else
                l = mid + 1;
        }

        a = {a[l]};
        swap(a, b);
    }

    if (a[0] > b[0])
        swap(a, b);
    return {a[0], b[0]};
}

void run(int _n){
    n = _n;
    for(int i = 1; i <= n; i++)
        root[i] = i;
    for(int i = 1; i < n; i++){
        pair <int, int> edge = findEdge();
        mySetRoad(edge.first, edge.second);
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 492 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 492 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 492 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 620 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 748 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 492 KB Wrong road!
2 Halted 0 ms 0 KB -