oj.uz

Submission #604751

# Submission time Handle Problem Language Result Execution time Memory
604751 2022-07-25T09:30:20 Z SlavicG ICC (CEOI16_icc) C++17
0 / 100
 24 ms 808 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 756 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 716 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 760 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 808 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 760 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -