Submission #1176677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176677		Irate	ICC (CEOI16_icc)	C++20	0 / 100	9 ms	584 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
const int mxN = 105;
struct DSU{
    vector<int>par;
    DSU(int n){
        par.assign(n + 1, -1);
    }
    int Find(int u){
        if(par[u] < 0)return u;
        return par[u] = Find(par[u]);
    }
    void Union(int u, int v){
        u = Find(u);
        v = Find(v);
        if(u == v)return;
        if(par[u] < par[v])swap(u, v);
        par[u] += par[v];
        par[v] = u;
    }
    bool isConnected(int u, int v){
        return Find(u) == Find(v);
    }
};
int Query(int sza, int szb, vector<int>a, vector<int>b){
    int A[sza], B[szb];
    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 run(int n){
    srand(time(0));
    DSU dsu(n);
    for(int k = 0;k < n - 1;++k){
        vector<int>V;
        for(int i = 1;i <= n;++i){
            if(dsu.Find(i) == i)V.push_back(i);
        }
        int node = -1, node2 = -1;
        vector<int>a, b;
        do{
            a.clear();
            b.clear();
            int indx = rand() % (int)V.size();
            node = V[indx];
            a.push_back(node);
            V.erase(V.begin() + indx);
            for(int x : V){
                if(!dsu.isConnected(node, x)){
                    b.push_back(x);
                }
            }
        }while(!Query(a.size(), b.size(), a, b) && !V.empty());
        int l = 0, r = b.size() - 1, ans = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            vector<int>temp;
            for(int i = 0;i <= mid;++i){
                temp.push_back(b[i]);
            }
            if(Query(a.size(), temp.size(), a, temp)){
                ans = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        node2 = b[ans];
        setRoad(node, node2);
        dsu.Union(node, node2);
    }
}

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