oj.uz

Submission #598036

# Submission time Handle Problem Language Result Execution time Memory
598036 2022-07-17T12:10:59 Z boris_mihov Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 31056 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF = 1e9 + 10;

int n, m;
int a[MAXN], s[MAXN], inS[MAXN];
std::vector < int > g[MAXN];

struct DSUelement
{
    int par;
    int sum;
    std::vector < int > alive;
} c[MAXN];

int find(int x)
{
    if (c[x].par == x) return x;
    return c[x].par = find(c[x].par);
}

void connect(int x, int y)
{
    x = find(x);
    y = find(y);
    if (c[x].alive.size() > c[y].alive.size()) std::swap(x, y);
    c[x].par = y;
    c[y].sum += c[x].sum;
    c[y].sum = std::min(c[y].sum, INF);
    c[y].alive.reserve(c[x].alive.size() + c[y].alive.size());
    for (int i : c[x].alive)
    {
        c[y].alive.push_back(i);
    }
}

bool areConnected(int x, int y)
{
    return find(x) == find(y);
}

char ans[MAXN];
void solve()
{
    std::iota(s+1, s+n+1, 1);
    std::sort(s+1, s+n+1, [&](int x, int y)
    {
        return a[x] < a[y];
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        inS[s[i]] = i;
        c[i].par = i;
        c[i].sum = a[i];
        c[i].alive.push_back(i);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        int x = s[i];
        for (const int &j : g[x])
        {
            if (inS[j] > i || areConnected(x, j)) continue;
            int par = find(j);
            if (c[par].sum < a[x])
            {
                c[par].alive.clear();
            }

            connect(x, j);
        }
    }

    int findPar = find(1);
    std::fill(ans, ans+n, '0');
    for (int i : c[findPar].alive)
    {
        ans[i-1] = '1';
    }

    ans[n] = '\0';
    std::cout << ans << '\n';
}

void read()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int x, y;
        std::cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 8 ms 11348 KB Output is correct
5 Correct 6 ms 11476 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 7 ms 11424 KB Output is correct
8 Correct 6 ms 11348 KB Output is correct
9 Correct 7 ms 11456 KB Output is correct
10 Correct 7 ms 11368 KB Output is correct
11 Correct 7 ms 11476 KB Output is correct
12 Correct 7 ms 11476 KB Output is correct
13 Correct 7 ms 11456 KB Output is correct
14 Correct 7 ms 11436 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 5 ms 11192 KB Output is correct
3 Execution timed out 1073 ms 29248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11220 KB Output is correct
2 Correct 183 ms 29628 KB Output is correct
3 Correct 184 ms 29528 KB Output is correct
4 Correct 174 ms 30928 KB Output is correct
5 Correct 167 ms 31056 KB Output is correct
6 Correct 192 ms 29580 KB Output is correct
7 Execution timed out 1088 ms 27232 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11220 KB Output is correct
2 Correct 900 ms 28312 KB Output is correct
3 Correct 413 ms 29468 KB Output is correct
4 Correct 228 ms 30224 KB Output is correct
5 Correct 550 ms 30944 KB Output is correct
6 Execution timed out 1031 ms 28960 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 8 ms 11348 KB Output is correct
5 Correct 6 ms 11476 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 7 ms 11424 KB Output is correct
8 Correct 6 ms 11348 KB Output is correct
9 Correct 7 ms 11456 KB Output is correct
10 Correct 7 ms 11368 KB Output is correct
11 Correct 7 ms 11476 KB Output is correct
12 Correct 7 ms 11476 KB Output is correct
13 Correct 7 ms 11456 KB Output is correct
14 Correct 7 ms 11436 KB Output is correct
15 Correct 5 ms 11220 KB Output is correct
16 Correct 5 ms 11192 KB Output is correct
17 Execution timed out 1073 ms 29248 KB Time limit exceeded
18 Halted 0 ms 0 KB -