oj.uz

답안 #606282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
606282 2022-07-26T05:58:57 Z drdilyor CEOI16_icc (CEOI16_icc) C++17
100 / 100
 132 ms 632 KB 
#include <bits/stdc++.h>
#ifdef ONPC
    #include "t_debug.cpp"
#else
    #define debug(...) 42
    #include "icc.h"
#endif
#define sz(a) ((int)(a).size())
using namespace std;
using ll = long long;
const int INF = 1e9;
const ll INFL = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(123);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
const int N = 100, LOGN = 17, MOD = 1e9+7;

int nextPower2(int n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return 1+n;
}

struct DSU {
    int n;
    vector<int> parent;
    vector<int> size;
    vector<vector<int>> full;

    DSU(int n) : n(n), parent(n), size(n, 1), full(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            full[i] = {i};
        }
    }

    int get(int i) {
        return parent[i] == i ? i : parent[i] = get(parent[i]);
    }

    void merge(int v, int u) {
        v = get(v);
        u = get(u);
        if (u == v) return;
        if (size[v] < size[u]) swap(v, u);
        parent[u] = v;
        size[v] += size[u];
        for (int j : full[u]) {
            full[v].push_back(j);
        }
    }
    inline vector<int> elems(int i) {
        return full[get(i)];
    }
};

#ifdef ONPC
void setRoad(int u, int v);
#endif
void confirm(int u, int v);
int query(vector<int>&, vector<int>&);
int query(vector<int>&&, vector<int>&&);

int myrand(int i) {
    return rng() % i;
}

void run(int n) {
    DSU cc(n);
    for (int e = 0; e < n-1; e++) {
        vector<vector<int>> comps;
        vector<int> visited(n);
        for (int i = 0; i < n; i++) {
            if (visited[cc.get(i)]) continue;
            comps.push_back(cc.full[cc.get(i)]);
            visited[cc.get(i)] = true;
        }
        sort(comps.begin(), comps.end(), [&](const vector<int>& a, const vector<int>& b) {
            return a.size() < b.size();});

        debug(cc.parent, cc.full);
        debug(comps);
        vector<int> a, b;
        bool found = false;

        vector<int> offs;
        for (int off =nextPower2(sz(comps)) >> 1; off; off >>= 1) {
            offs.push_back(off);
        }

        random_shuffle(offs.begin(), offs.end(), myrand);

        function<tuple<vector<int>,vector<int>>(int)> partition = [&](int off) {
            vector<int> a, b;
            for (int i = 0; i < sz(comps); i++) {
                if (i / off % 2 == 0) {
                    for (int j : comps[i]) a.push_back(j);
                } else {
                    for (int j : comps[i]) b.push_back(j);
                }
            }
            return tuple<vector<int>,vector<int>>{a, b};
        };

        for (int i = 0; i < sz(offs)-1; i++) {
            tie(a, b) = partition(offs[i]);
            if (query(a, b)) {found = true;break;}
        }
        if (!found) {
            tie(a, b) = partition(offs.back());
        }

        while (sz(a) > 1) {
            vector<int> a2;
            for (int i = 0; i < sz(a) / 2; i++) {
                a2.push_back(a[i]);
            }
            debug(a, a2);
            if (!query(a2, b)) {
                a2.clear();
                for (int i = sz(a) / 2; i < sz(a); i++) {
                    a2.push_back(a[i]);
                }
            }
            a = a2;
        }
        while (sz(b) > 1) {
            vector<int> b2;
            for (int i = 0; i < sz(b) / 2; i++) {
                b2.push_back(b[i]);
            }
            if (!query(b2, a)) {
                b2.clear();
                for (int i = sz(b) / 2; i < sz(b); i++) {
                    b2.push_back(b[i]);
                }
            }
            b = b2;
        }
        cc.merge(a.front(), b.front());
        confirm(a.front(), b.front());
    }
}

#ifdef ONPC

int n, m;
bool adj[N][N];
vector<pair<int,int>> edges;
int cur = 0;
int query_count = 0;

int query(vector<int>& a, vector<int>& b) {
    ++query_count;
    bool res = false;
    for (int i : a) {
        for (int j : b) {
            assert(i != j);
            if (adj[i][j])res = true;
        }
    }

    return res;
}


void advance() {
    if (cur < sz(edges)) {
        auto [u,v] = edges[cur];
        adj[u][v] = adj[v][u] = true;
        cur++;
    }
}

void setRoad(int u, int v) {
    if (u > v) swap(u, v);
    if (edges[cur-1].first != u || edges[cur-1].second != v) {
        debug("wrong guess", cur, edges[cur-1], u, v);
    }
    advance();
}

int solve() {
    cin >> n >> m;
    if (!cin) return 1;
    memset(adj, 0, sizeof(adj));
    edges.clear();

    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        if (u > v) swap(u, v);
        edges.emplace_back(u, v);
    }
    debug(edges);
    advance();
    run(n);
    assert(cur == n-1);
    debug(query_count);
    return 0;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    #ifdef ONPC
    t = 10000;
    #endif
    while (t-- && cin) {
        if (solve()) break;
        #ifdef ONPC
            cout << "____________________" << endl;
        #endif
    }
    return 0;
}
#else
int query(vector<int>& a, vector<int>& b) {
    vector<int> a2 = a, b2 = b;
    for (auto& i : a2) i++;
    for (auto& i : b2) i++;
    return query(a.size(), b.size(), a2.data(), b2.data());
}

#endif

void confirm(int u, int v){
#ifndef ONPC
    u++; v++;
#endif
    setRoad(u, v);
}


int query(vector<int>&& a, vector<int>&& b) {
    return query(a, b);
}

/*
     █████               █████  ███  ████                               
    ▒▒███               ▒▒███  ▒▒▒  ▒▒███                               
  ███████  ████████   ███████  ████  ▒███  █████ ████  ██████  ████████ 
 ███▒▒███ ▒▒███▒▒███ ███▒▒███ ▒▒███  ▒███ ▒▒███ ▒███  ███▒▒███▒▒███▒▒███
▒███ ▒███  ▒███ ▒▒▒ ▒███ ▒███  ▒███  ▒███  ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒▒ 
▒███ ▒███  ▒███     ▒███ ▒███  ▒███  ▒███  ▒███ ▒███ ▒███ ▒███ ▒███     
▒▒████████ █████    ▒▒████████ █████ █████ ▒▒███████ ▒▒██████  █████    
 ▒▒▒▒▒▒▒▒ ▒▒▒▒▒      ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒   ▒▒▒▒▒███  ▒▒▒▒▒▒  ▒▒▒▒▒     
                                            ███ ▒███                    
                                           ▒▒██████                     
                                            ▒▒▒▒▒▒
*/

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:5:24: warning: statement has no effect [-Wunused-value]
    5 |     #define debug(...) 42
      |                        ^~
icc.cpp:85:9: note: in expansion of macro 'debug'
   85 |         debug(cc.parent, cc.full);
      |         ^~~~~
icc.cpp:5:24: warning: statement has no effect [-Wunused-value]
    5 |     #define debug(...) 42
      |                        ^~
icc.cpp:86:9: note: in expansion of macro 'debug'
   86 |         debug(comps);
      |         ^~~~~
icc.cpp:5:24: warning: statement has no effect [-Wunused-value]
    5 |     #define debug(...) 42
      |                        ^~
icc.cpp:122:13: note: in expansion of macro 'debug'
  122 |             debug(a, a2);
      |             ^~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Ok! 98 queries used.
2 Correct 5 ms 468 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 484 KB Ok! 543 queries used.
2 Correct 32 ms 468 KB Ok! 635 queries used.
3 Correct 32 ms 468 KB Ok! 642 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 500 KB Ok! 1454 queries used.
2 Correct 105 ms 500 KB Ok! 1585 queries used.
3 Correct 104 ms 504 KB Ok! 1561 queries used.
4 Correct 127 ms 520 KB Ok! 1549 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 516 KB Ok! 1552 queries used.
2 Correct 129 ms 468 KB Ok! 1557 queries used.
3 Correct 99 ms 516 KB Ok! 1572 queries used.
4 Correct 99 ms 512 KB Ok! 1493 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 508 KB Ok! 1574 queries used.
2 Correct 107 ms 468 KB Ok! 1584 queries used.
3 Correct 102 ms 516 KB Ok! 1583 queries used.
4 Correct 104 ms 500 KB Ok! 1577 queries used.
5 Correct 106 ms 504 KB Ok! 1509 queries used.
6 Correct 109 ms 504 KB Ok! 1571 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 632 KB Ok! 1590 queries used.
2 Correct 104 ms 496 KB Ok! 1584 queries used.