oj.uz

Submission #851756

# Submission time Handle Problem Language Result Execution time Memory
851756 2023-09-20T14:28:48 Z c2zi6 Zamjene (COCI16_zamjene) C++14
0 / 140
 6000 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7639 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7621 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7700 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7654 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7837 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6013 ms 87788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6011 ms 87408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6031 ms 166588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6080 ms 275916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6103 ms 266596 KB Time limit exceeded
2 Halted 0 ms 0 KB -