oj.uz

Submission #580152

# Submission time Handle Problem Language Result Execution time Memory
580152 2022-06-20T16:14:51 Z Josia Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 70268 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t


struct unionfindElem {
    int chef;
    int amount;
    set<int> active;
};

bool compare(unionfindElem A, unionfindElem B) {
    tuple<int, int, set<int>> a = {A.chef, A.amount, A.active};
    tuple<int, int, set<int>> b = {B.chef, B.amount, B.active};
    return a<b;
}



vector<unionfindElem> chefs;

void init(vector<pair<int, int>> vilages) {
    for (pair<int, int> i: vilages) {
        chefs.push_back({i.second, i.first, {i.second}});
    }
    sort(chefs.begin(), chefs.end(), compare);
}


int find(int x) {
    if (chefs[x].chef == x) return x;
    return chefs[x].chef = find(chefs[x].chef);
}


void Merge(set<int>& a, set<int>& b) {
    if (a.size() > b.size()) {
        swap(a, b);
    }
    for (int i: a) b.insert(i);
}


void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;

    chefs[a].chef = b;
    chefs[b].amount += chefs[a].amount;
    Merge(chefs[a].active, chefs[b].active);
}



signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n; int m; cin >> n >> m;

    vector<pair<int, int>> vilages(n);
    vector<int> inhabitants(n);

    for (int i = 0; i<n; i++) {
        cin >> vilages[i].first;
        inhabitants[i] = vilages[i].first;
        vilages[i].second = i;
    }

    sort(vilages.begin(), vilages.end());

    vector<vector<int>> graph(n);

    for (int i = 0; i<m; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    init(vilages);


    vector<int> newcomers;
    for (auto pii: vilages) {
        int i = pii.second;
        newcomers.push_back(i);
        
        for (int j: graph[i]) {
            if (inhabitants[i] > chefs[find(j)].amount) chefs[find(j)].active.clear();
            if (inhabitants[i] >= inhabitants[j]) unite(i, j);
        }
        // for (auto chef: chefs) {
        //     for (int i: chef.active) cerr << i << " ";
        //     cerr << "\n";
        //     cerr << chef.chef << " " << chef.amount << "\n";
        // }
        // cerr << "\n";
    }

    vector<int> res(n);

    auto chef = chefs[find(0)];
    for (int i: chef.active) res[i] = 1;

    for (int i: res) cout << i;
    cout << "\n";


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 744 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 852 KB Output is correct
11 Correct 6 ms 852 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 9 ms 780 KB Output is correct
14 Correct 6 ms 852 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 586 ms 54400 KB Output is correct
4 Execution timed out 1082 ms 42648 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 957 ms 70244 KB Output is correct
3 Correct 991 ms 70268 KB Output is correct
4 Execution timed out 1094 ms 41652 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 972 ms 57668 KB Output is correct
3 Execution timed out 1014 ms 60860 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 744 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 852 KB Output is correct
11 Correct 6 ms 852 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 9 ms 780 KB Output is correct
14 Correct 6 ms 852 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 586 ms 54400 KB Output is correct
18 Execution timed out 1082 ms 42648 KB Time limit exceeded
19 Halted 0 ms 0 KB -