oj.uz

Submission #465296

# Submission time Handle Problem Language Result Execution time Memory
465296 2021-08-15T14:06:22 Z Mamedov ICC (CEOI16_icc) C++17
100 / 100
 159 ms 580 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "icc.h"
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define pis pair<int, string>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DSU {
    vector<int>root;
    vector<vector<int>>group;
    DSU(int n) {
        group.resize(n + 1);
        root.resize(n + 1);
        for(int i = 1; i <= n; ++i) {
            group[i].clear();
            group[i].pb(i);
            root[i] = i;
        }
    }

    void Union(int u, int v) {
        u = root[u];
        v = root[v];
        if(group[u].size() < group[v].size()) {
            swap(u, v);
        }
        for(int node : group[v]) {
            root[node] = u;
            group[u].pb(node);
        }
        group[v].clear();
    }
};

void solve(int &size_a, int size_b, int a[], int b[]) {
    if(size_a > 1) {
        if(query(size_a / 2, size_b, a, b)) {
            size_a /= 2;
        }else {
            int pos = 0;
            for(int i = size_a / 2; i < size_a; ++i) {
                a[pos++] = a[i];
            }
            size_a = pos;
        }
        solve(size_a, size_b, a, b);
    }
}

const int SIZE = 101;
int Query(vector<int> &roots_a, vector<int> &roots_b, DSU &dsu, int i, int j, bool found) {
    int a[SIZE], b[SIZE];
    int size_a = 0, size_b = 0;
    for(int k = i; k <= j; ++k) {
        int r = roots_a[k];
        if(r == 0) continue;
        for(int node : dsu.group[r]) {
            a[size_a++] = node;
        }
    }
    for(int k = i; k <= j; ++k) {
        int r = roots_b[k];
        if(r == 0) continue;
        for(int node : dsu.group[r]) {
            b[size_b++] = node;
        }
    }
    if(found) {
        solve(size_a, size_b, a, b);
        solve(size_b, size_a, b, a);
        setRoad(a[0], b[0]);
        dsu.Union(a[0], b[0]);
        return 1;
    }
    else if(query(size_a, size_b, a, b)) {
        return 1;
    }else {
        return 0;
    }
}

void solve(int n, DSU &dsu) {
    vector<int>roots_a, roots_b;
    int pw = 1;
    for(int i = 1; i <= n; ++i) {
        if(dsu.root[i] == i) {
            if(roots_a.size() <= roots_b.size()) {
                roots_a.pb(i);
            }else {
                roots_b.pb(i);
            }
            if(pw < (int)roots_a.size()) pw <<= 1;
        }
    }

    int res = 0;
    int sza = (int)roots_a.size();
    int szb = (int)roots_b.size();
    while(sza < pw) {
        roots_a.pb(0);
        ++sza;
    }
    while(szb < pw) {
        roots_b.pb(0);
        ++szb;
    }
    int jump;
    for(jump = sza; !res; jump >>= 1) {
        int pos = jump;
        while(pos < sza) {
            swap(roots_a[pos], roots_b[pos]);
            ++pos;
            if(pos % jump == 0) pos += jump;
        }
        res = Query(roots_a, roots_b, dsu, 0, sza - 1, false);
        if(res) {
            int l = 0, r = sza - 1;
            int mid;
            while(r - l + 1 >= 4 * jump) {
                mid = (l + r) >> 1;
                if(Query(roots_a, roots_b, dsu, l, mid, false)) {
                    r = mid;
                }else {
                    l = mid + 1;
                }
            }
            Query(roots_a, roots_b, dsu, l, r, true);
        }
    }
}

void run(int n) {
    DSU dsu(n);
    for(int i = 1; i < n; ++i) {
        solve(n, dsu);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 488 KB Ok! 94 queries used.
2 Correct 9 ms 492 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 460 KB Ok! 559 queries used.
2 Correct 47 ms 476 KB Ok! 626 queries used.
3 Correct 46 ms 376 KB Ok! 621 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 480 KB Ok! 1465 queries used.
2 Correct 149 ms 476 KB Ok! 1499 queries used.
3 Correct 148 ms 476 KB Ok! 1554 queries used.
4 Correct 146 ms 488 KB Ok! 1516 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 480 KB Ok! 1517 queries used.
2 Correct 151 ms 480 KB Ok! 1471 queries used.
3 Correct 144 ms 488 KB Ok! 1534 queries used.
4 Correct 159 ms 480 KB Ok! 1471 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 484 KB Ok! 1568 queries used.
2 Correct 145 ms 488 KB Ok! 1532 queries used.
3 Correct 150 ms 484 KB Ok! 1526 queries used.
4 Correct 144 ms 460 KB Ok! 1540 queries used.
5 Correct 139 ms 488 KB Ok! 1457 queries used.
6 Correct 144 ms 580 KB Ok! 1503 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 488 KB Ok! 1535 queries used.
2 Correct 156 ms 472 KB Ok! 1607 queries used.