Submission #1176635

#TimeUsernameProblemLanguageResultExecution timeMemory
1176635IrateICC (CEOI16_icc)C++20
7 / 100
173 ms620 KiB
#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];
    }
    int num = query(sza, szb, A, B);
    return num;
}
void run(int n){
    srand(time(0));
    DSU dsu(n);
    for(int k = 0;k < n - 1;++k){
        int node = -1, node2 = -1;
        for(int i = 1;i <= n;++i){
            vector<int>a = {i}, b;
            for(int j = i + 1;j <= n;++j){
                if(dsu.isConnected(i, j))continue;
                b.push_back(j);
            }
            if(Query(a.size(), b.size(), a, b)){
                node = i;
                break;
            }
        }
        for(int i = 1;i <= n;++i){
            if(dsu.isConnected(node, i))continue;
            vector<int>a = {node}, temp = {i};
            if(Query(a.size(), temp.size(), a, temp)){
                node2 = i;
                break;
            }
        }
        setRoad(node, node2);
        dsu.Union(node, node2);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...