oj.uz

Submission #722590

# Submission time Handle Problem Language Result Execution time Memory
722590 2023-04-12T12:03:36 Z Itamar Stranded Far From Home (BOI22_island) C++14
10 / 100
 528 ms 65708 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]) {
            pi p1 = { cit[f],num[f] }, p2 = { cit[i], num[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; 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]) {
            pi p1 = { cit[f],num[f] }, p2 = { cit[j], num[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

Compilation message

island.cpp: In function 'int main()':
island.cpp:74:16: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
   74 |             pi p1 = { cit[f],num[f] }, p2 = { cit[i], num[i] };
      |                ^~
island.cpp:74:40: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
   74 |             pi p1 = { cit[f],num[f] }, p2 = { cit[i], num[i] };
      |                                        ^~
island.cpp:89:16: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
   89 |             pi p1 = { cit[f],num[f] }, p2 = { cit[j], num[j] };
      |                ^~
island.cpp:89:40: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
   89 |             pi p1 = { cit[f],num[f] }, p2 = { cit[j], num[j] };
      |                                        ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Incorrect 13 ms 19412 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 19092 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 361 ms 54856 KB Output is correct
4 Correct 288 ms 55024 KB Output is correct
5 Correct 451 ms 61712 KB Output is correct
6 Correct 459 ms 63020 KB Output is correct
7 Correct 488 ms 63020 KB Output is correct
8 Correct 480 ms 62424 KB Output is correct
9 Correct 361 ms 65708 KB Output is correct
10 Correct 379 ms 59056 KB Output is correct
11 Correct 391 ms 59060 KB Output is correct
12 Correct 397 ms 61104 KB Output is correct
13 Correct 270 ms 57900 KB Output is correct
14 Correct 279 ms 57952 KB Output is correct
15 Correct 330 ms 59360 KB Output is correct
16 Correct 234 ms 58364 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 485 ms 53196 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 528 ms 53252 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 9 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Incorrect 13 ms 19412 KB Output isn't correct
5 Halted 0 ms 0 KB -