Submission #851756

#	Time	Username	Problem	Language	Result	Execution time	Memory
851756		c2zi6	Zamjene (COCI16_zamjene)	C++14	0 / 140	7837 ms	524288 KiB

zamjene

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

vector<int> a, q;

vector<int> p;
vector<int> cnt;
vector<map<int, int>> seq;
int LAVCNT;

int get(int u) {
    return p[u] = (u == p[u] ? u : get(p[u]));
}

void onion(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) return;

    if (cnt[v] > cnt[u]) swap(u, v);

    //v-n miacnel u-in
    cnt[u] += cnt[v];
    p[v] = u;

    if (seq[u].size() == 0) LAVCNT--;
    if (seq[v].size() == 0) LAVCNT--;
    for (pair<int, int> p : seq[v]) {
        seq[u][p.first] += p.second;
        if (seq[u][p.first] == 0) seq[u].erase(p.first);
    }
    if (seq[u].size() == 0) LAVCNT++;
}

void solve() {
    int n, Q;
    cin >> n >> Q;
    a = vector<int>(n);
    for (int& x : a) cin >> x;
    q = a;
    sort(q.begin(), q.end());

    LAVCNT = 0;
    p = cnt = vector<int>(n);
    seq = vector<map<int, int>>(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
        cnt[i] = 1;
        if (a[i] == q[i]) {
            LAVCNT++;
            continue;
        }
        seq[i][a[i]]++;
        seq[i][q[i]]--;
    }

    while (true) {
        cout << "type: ";
        int t;
        cin >> t;
        if (t == 1) {
            set<int> st;
            for (int i = 0; i < n; i++) {
                cout << get(i) << " ";
                st.insert(get(i));
            }
            cout << endl;
            cout << "GOOD CLOUDS' COUNT: " << LAVCNT << endl;
            for (int x : st) {
                cout << x << "'s properties:" << endl;
                cout << "   count: " << cnt[x] << endl;
                for (pair<int, int> p : seq[x]) {
                    cout << "   " << p.first << ": " << p.second << endl;
                }
            }
        } else {
            int u, v;
            cin >> u >> v;
            onion(u, v);
        }
    }
}

int main() {
    int t = 1;
    //cin >> t;
    while (t--) solve();
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14