oj.uz

Submission #722599

# Submission time Handle Problem Language Result Execution time Memory
722599 2023-04-12T12:16:48 Z Itamar Stranded Far From Home (BOI22_island) C++14
10 / 100
 529 ms 60592 KB 
// ConsoleApplication134.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define pi pair<int,int>
#define ll long long
#include <algorithm>
#include <queue>
#define pll pair<ll,ll>
const int siz = 2e5;
bool ans[siz];
ll cit[siz];
vi fr[siz];
int up[siz];
#include <set>
vector<pll> ord;

int my[siz];
vi col[siz];
ll sum[siz];
set<pll> out[siz];

int num[siz];
void uni(int i, int j) {
    if (my[i] == my[j])return;
    if (out[my[i]].size() < out[my[j]].size()) {
        swap(out[my[i]], out[my[j]]);
    }
    if (col[my[i]].size() < col[my[j]].size()) {
        swap(col[my[i]], col[my[j]]);
    }
    for (int v : col[my[j]]) {
        col[my[i]].push_back(v);
    }
    for (pll p : out[my[j]]) {
        out[my[i]].insert(p);
    }
    sum[my[i]] += sum[my[j]];
    for (int v : col[my[j]]) {
        my[v] = my[i];
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> cit[i];
        ord.push_back({ cit[i],-i });
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        fr[a].push_back(b);
        fr[b].push_back(a);
    }
    sort(ord.begin(), ord.end());
    ans[-ord[n - 1].second] = 1;
    for (int i = 0; i < n; i++) {
        ord[i].second = -ord[i].second;
        num[ord[i].second] = i;
    }
    for (int i = 0; i < n; i++) {
        my[i] = i;
        col[i].push_back(i);
        sum[i] = cit[i];
        
        for (int f : fr[i]) {
            if ( num[f]>num[i]) {
                out[i].insert({ cit[f],f });
            }
        }
    }                
    for (int i = 0; i < n; i++)up[i] = -1;
    for (int i = 0; i < n-1; i++) {
        int j = ord[i].second;
        for (int f : fr[j]) {
            if (out[my[f]].find({ cit[j],j }) != out[my[f]].end()) {
                out[my[f]].erase({ cit[j],j });
            }
        }
        for (int f : fr[j]) {
            if (num[f] < i) {
                uni(j, f);
            }
        }
        if (!out[my[j]].empty()) {
            pll p = *out[my[j]].begin();
            if (p.first <= sum[my[j]]) {
                up[j] = p.second;
            }
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        if (up[ord[i].second] != -1) {
            ans[ord[i].second] = ans[up[ord[i].second]];
        }
    }
    for (int i = 0; i < n; i++)if (ans[i])cout << '1'; else cout << '0';
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19088 KB Output is correct
3 Correct 11 ms 19028 KB Output is correct
4 Incorrect 12 ms 19448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19072 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 353 ms 54956 KB Output is correct
4 Correct 303 ms 54960 KB Output is correct
5 Correct 417 ms 57400 KB Output is correct
6 Correct 455 ms 58728 KB Output is correct
7 Correct 487 ms 58664 KB Output is correct
8 Correct 465 ms 57980 KB Output is correct
9 Correct 326 ms 60592 KB Output is correct
10 Correct 260 ms 53716 KB Output is correct
11 Correct 284 ms 53948 KB Output is correct
12 Correct 403 ms 58076 KB Output is correct
13 Correct 292 ms 54828 KB Output is correct
14 Correct 293 ms 54932 KB Output is correct
15 Correct 344 ms 54848 KB Output is correct
16 Correct 233 ms 54592 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Incorrect 529 ms 53180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Incorrect 505 ms 53200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19088 KB Output is correct
3 Correct 11 ms 19028 KB Output is correct
4 Incorrect 12 ms 19448 KB Output isn't correct
5 Halted 0 ms 0 KB -