제출 #948816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948816		tmarcinkevicius	Stranded Far From Home (BOI22_island)	C++14	0 / 100	1056 ms	78268 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;

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;
    parWSum[a] += parWSum[b];
    for (int i : membersAtPar[b])
    {
        membersAtPar[a].push_back(i);
    }

    return true;
}

void MarkWinFalse(int n)
{
    //cout << "mark component " << n << " to false:";
    for (int i : membersAtPar[n])
    {
        //cout << "set " << i << " to false\n";
        canWin[i] = false;
    }
}


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);

    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));

            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:113:13: warning: unused variable 'currVal' [-Wunused-variable]
  113 |         int currVal = (*it).f;
      |             ^~~~~~~

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