oj.uz

Submission #948836

# Submission time Handle Problem Language Result Execution time Memory
948836 2024-03-18T15:10:24 Z tmarcinkevicius Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 81712 KB 
#include <bits/stdc++.h>  
using namespace std;

#define int int64_t
typedef pair<int,int> pii;
typedef vector<int> vii;
#define MP make_pair
#define PB push_back
#define f first
#define s second
#define INF 2e18
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())

vector<int> canWin;
vector<int> par;
vector<int> parWSum;
vector<vector<int>> membersAtPar;
vector<vector<int>> children;

int N, M;
vector<int> w;
int maxComp = 0;

int Parent(int n)
{
    if (par[n] == n || par[n] == -1)
    {
        return par[n];
    }

    return Parent(par[n]);
}

void CreateNode(int n)
{
    par[n] = n;
    parWSum[n] = w[n];
    membersAtPar[n].push_back(n);
}

bool Join(int a, int b)
{
    if (a == b)
        return false;

    //cout << "Join(" << a << " " << b << ")\n";

    if (membersAtPar[b].size() > membersAtPar[a].size())
    {
        swap(a, b);
    }

    par[b] = a;
    children[a].push_back(b);
    parWSum[a] += parWSum[b];
    for (int i : membersAtPar[b])
    {
        membersAtPar[a].push_back(i);
    }

    return true;
}

void MarkWinFalse(int n)
{
    //if (!canWin[n])
    //    return;

    //cout << "mark false(" << n << ")\n";

    canWin[n] = false;
    for (int i : children[n])
    {
        MarkWinFalse(i);
    }
}


int32_t main()
{
    fast_io();

    cin >> N >> M;

    canWin = vector<int>(N + 1, true);
    par = vector<int>(N + 1, -1);
    w = vector<int>(N + 1);
    membersAtPar = vector<vector<int>>(N + 1);
    parWSum = vector<int>(N + 1);
    children = vector<vector<int>>(N + 1);

    for (int i = 1; i <= N; i++)
    {
        cin >> w[i];
    }

    auto w2 = w;
    sort(all(w2));

    map<int, vector<pii>> paths;
    map<int, vector<int>> verticies;

    for (int i = 1; i <= N; i++)
    {
        verticies[w[i]].push_back(i);
    }

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        paths[max(w[a], w[b])].push_back({a, b});
    }

    for (auto it = verticies.begin(); next(it) != verticies.end(); ++it)
    {
        //cout << "now it(1): " << (*it).f << '\n';
        int currVal = (*it).f;

        for (int ver : (*it).s)
        {
            CreateNode(ver);
        }
        for (pii &edge : paths[(*it).f])
        {
            //cout << "edge: {" << edge.f << ", " << edge.s << "}\n";

            Join(Parent(edge.f), Parent(edge.s));
        }

        int nextVal = (*next(it)).f;
        for (int ver : (*it).s)
        {
            int parent = Parent(ver);
            // assert(edge.f == Parent(edge.f));
            // assert(edge.s == Parent(edge.s));

            //cout << "analyze parent: " << parent << '\n';
            //cout << "nextVal = " << nextVal << '\n';

            if (parWSum[parent] < nextVal)
            {
                MarkWinFalse(parent);
            }
        }

        //cout << "now it(2): " << (*it).f << '\n';

        //cout << "curr = " << currVal << ", next = " << nextVal << '\n';

        /*for (int i = 1; i <= N; i++)
        {
            cout << "par[" << i << "] = " << par[i] << '\n';
        }*/
    }

    for (int i = 1; i <= N; i++)
    {
        cout << canWin[i];
    }
    cout << '\n';
}

Compilation message

island.cpp: In function 'int32_t main()':
island.cpp:120:13: warning: unused variable 'currVal' [-Wunused-variable]
  120 |         int currVal = (*it).f;
      |             ^~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 274 ms 71784 KB Output is correct
4 Execution timed out 1028 ms 44712 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 344 KB Output is correct
2 Incorrect 520 ms 81712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 130 ms 34104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -