제출 #948854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948854		tmarcinkevicius	Stranded Far From Home (BOI22_island)	C++14	100 / 100	583 ms	87184 KiB

island

#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(); 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";

            if (w[edge.f] < w[edge.s])
                swap(edge.f, edge.s);

            int parF = Parent(edge.f);
            int parS = Parent(edge.s);

            //cout << parS << " par sum: " << parWSum[parS] << '\n';
            //cout << "w[" << edge.f << "] = " << w[edge.f] << '\n';

            if (parWSum[parS] < w[edge.f])
            {
                MarkWinFalse(parS);
            }

            Join(parF, parS);
        }

        /*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';
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35