oj.uz

Submission #733399

# Submission time Handle Problem Language Result Execution time Memory
733399 2023-04-30T16:23:02 Z speedyArda Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 39540 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 2e5+5;
ll in[MAXN], sum[MAXN];
int ans[MAXN], par[MAXN];
vector<int> unprocessed[MAXN];
int find(int v)
{
    if(v == par[v])
        return v;
    return par[v] = find(par[v]);
}

int merge(int a, int b)
{
    a = find(a), b = find(b);
    if(a == b)
        return a;
    if(unprocessed[a].size() < unprocessed[b].size())
        swap(a, b);
    for(int e : unprocessed[b])
        unprocessed[a].push_back(e);
    sum[a] += sum[b];
    sum[b] = 0;
    par[b] = a;
    unprocessed[b].clear();
    return a;
}
vector < vector< int > > adj(MAXN);
int main() 
{
    set<int> available;
    int n, m;
    cin >> n >> m;
    vector < pair<int, int> > sorted;
    for(int i = 1; i <= n; i++) {
        cin >> in[i];
        sorted.push_back({in[i], i});
        ans[i] = 1;
        sum[i] = in[i];
        par[i] = i;
        unprocessed[i].push_back(i);
    }
    sort(sorted.begin(), sorted.end());
    for(int i = 1; i <= m; i++)
    {
        int f, s;
        cin >> f >> s;
        adj[f].push_back(s);
        adj[s].push_back(f);
    }

    int last = 0;
    for(int i = 0; i < n; i++) 
    {
        last = i;
        while(i < n && sorted[last].first == sorted[i].first)
            i++;
        i--;
        while(last <= i)
        {
            int idx = sorted[last].second;
            //cout << in[idx] << " " << idx << "\n";
            for(int e : adj[idx])
            {
                if(in[e] <= in[idx]) {
                    merge(e, idx);
                    //cout << e << " " << idx << "\n";
                }
            }
            //cout << find(idx) << "\n";
            available.insert(find(idx));
            last++;
        }



        if(i < n - 1)
        {
            int pass = sorted[i + 1].first;
            vector<int> remove;
            for(int e : available)
            {
                //cout << i << " " << e << " " << sum[e] << "\n";
                if(sum[e] < pass)
                {
                    remove.push_back(e);
                    for(int j : unprocessed[e])
                        ans[j] = 0;
                }
            }

            for(int e : remove)
            {
                available.erase(e);
            }
        }
    }



    for(int i = 1; i <= n; i++)
        cout << ans[i];
    cout << "\n";

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9720 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 9 ms 9856 KB Output is correct
5 Correct 9 ms 9972 KB Output is correct
6 Correct 8 ms 9840 KB Output is correct
7 Correct 8 ms 9940 KB Output is correct
8 Correct 12 ms 9932 KB Output is correct
9 Correct 7 ms 9940 KB Output is correct
10 Correct 9 ms 9984 KB Output is correct
11 Correct 11 ms 9940 KB Output is correct
12 Correct 9 ms 9940 KB Output is correct
13 Correct 7 ms 9940 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9652 KB Output is correct
2 Correct 5 ms 9688 KB Output is correct
3 Correct 363 ms 34892 KB Output is correct
4 Correct 247 ms 33588 KB Output is correct
5 Execution timed out 1088 ms 32456 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1065 ms 33032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 491 ms 37744 KB Output is correct
3 Correct 466 ms 38164 KB Output is correct
4 Correct 442 ms 39540 KB Output is correct
5 Correct 445 ms 39460 KB Output is correct
6 Correct 379 ms 36608 KB Output is correct
7 Correct 292 ms 35676 KB Output is correct
8 Correct 216 ms 33676 KB Output is correct
9 Correct 243 ms 24640 KB Output is correct
10 Correct 341 ms 39300 KB Output is correct
11 Correct 326 ms 35872 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9720 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 9 ms 9856 KB Output is correct
5 Correct 9 ms 9972 KB Output is correct
6 Correct 8 ms 9840 KB Output is correct
7 Correct 8 ms 9940 KB Output is correct
8 Correct 12 ms 9932 KB Output is correct
9 Correct 7 ms 9940 KB Output is correct
10 Correct 9 ms 9984 KB Output is correct
11 Correct 11 ms 9940 KB Output is correct
12 Correct 9 ms 9940 KB Output is correct
13 Correct 7 ms 9940 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 5 ms 9652 KB Output is correct
16 Correct 5 ms 9688 KB Output is correct
17 Correct 363 ms 34892 KB Output is correct
18 Correct 247 ms 33588 KB Output is correct
19 Execution timed out 1088 ms 32456 KB Time limit exceeded
20 Halted 0 ms 0 KB -