제출 #1180797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180797		kilikuma	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	328 KiB

bridge

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

int N, P[151];

int F(int u) {
    while (P[u] != u) P[u] = P[P[u]], u = P[u];
    return u;
}

void U(int u, int v) {
    int a = F(u), b = F(v);
    if (a != b) P[b] = a;
}

void find_same_color(int x, vector<int>& groups) {
    int l = 0, r = groups.size() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        cout << "2 " << groups[m] << ' ' << x << endl;
        int R; cin >> R;
        if (R == 1) {
            U(groups[m], x);
            return;
        } else {
            l = m + 1;
        }
    }
}

void D(vector<int> f) {
    if (f.size() == 1) return;
    int m = f.size() / 2;
    vector<int> l(f.begin(), f.begin() + m), r(f.begin() + m, f.end());
    D(l), D(r);
    
    map<int, vector<int>> group_map;
    for (int x : l) group_map[F(x)].push_back(x);
    
    for (int x : r) {
        if (group_map.empty()) break;
        cout << group_map.size() + 1 << ' ';
        for (auto& [k, v] : group_map) cout << v[0] << ' ';
        cout << x << endl;
        int R; cin >> R;
        if (R < group_map.size() + 1) {
            for (auto& [k, v] : group_map) {
                find_same_color(x, v);
                if (F(x) == k) break;
            }
        }
    }
}

int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) P[i] = i;
    vector<int> f(N); iota(f.begin(), f.end(), 1);
    D(f);
    map<int, int> m; int c = 0;
    cout << "0 ";
    for (int i = 1; i <= N; ++i) {
        int r = F(i);
        if (!m.count(r)) m[r] = ++c;
        cout << m[r] << ' ';
    }
    cout << endl;
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37