제출 #604751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604751		SlavicG	ICC (CEOI16_icc)	C++17	0 / 100	24 ms	808 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

/*
int query(int a, int b, int* aa, int* bb) {

}
*/

struct dsu {
    vector<int> p;
    dsu(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int get(int a) {return p[a] = (p[a] == a ? a : get(p[a]));}
    void uni(int a, int b) {
        a = get(a);
        b = get(b);
        p[a] = b;
    }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void run(int n) {
    dsu d(n + 5);
    for(int times = 0; times < n - 1; ++times) {
        int st = -1;
        vector<int> v;
        for(int i = 1; i <= n; ++i) v.push_back(i);
        shuffle(v.begin(), v.end(), rng);
        for(int i = 0; i + 1 < (int)v.size(); ++i) {
            int a = i + 1;
            int aa[a];
            vector<int> f;
            vector<bool> vis(n + 1, false);
            for(int j = 0; j <= i; ++j) {
                aa[j] = v[j];
                vis[d.get(v[j])] = true;
            }
            for(int j = i + 1; j < (int)v.size(); ++j) {
                if(vis[d.get(v[j])]) continue;
                f.push_back(v[j]);
            }
            int b = f.size();
            int bb[b];
            for(int j = 0; j < b; ++j) bb[j] = f[j];
            if(query(a, b, aa, bb)) {
                st = i;
                break;
            }
        }
        assert(st != -1);
        vector<bool> vis(n + 1, false);
        for(int j = 0; j <= st; ++j) vis[d.get(v[j])] = true;
        for(int i = st + 1; i < (int)v.size(); ++i) {
            int a[1], b[1];
            a[0] = v[st];
            b[0] = v[i];
            if(vis[d.get(b[0])]) continue;
            if(query(1, 1, a, b)) {
                d.uni(a[0], b[0]);
                setRoad(a[0], b[0]);
                break;
            }
        }
    }
}

/*
int main() {
    int n; cin >> n;
    run(n);
}
*/

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