제출 #674899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674899		Tigerpants	Stranded Far From Home (BOI22_island)	C++17	100 / 100	682 ms	100224 KiB

island

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef set<ll> sll;
typedef vector<sll> vsll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef set<pll> spll;
typedef vector<spll> vspll;
typedef vector<bool> vb;

#define rep(x, a, b) for (int x = a; x < b; x++)
#define rep_itr(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, b) a.resize(b)
#define sort_all(a) sort(all(a))

const ll MAXN = 200000;
const ll MAXM = 200000;

ll N, M;
vll s;
vsll g;

vb active;
vll ptr_comp;
vll sz_comp;
vsll takeover;
vll sum_comp;

ll find_par(ll x) {
    ll y = x;
    while (x != ptr_comp[x]) {
        x = ptr_comp[x];
    }
    ptr_comp[y] = x;
    return x;
}

void merge(ll x, ll y) { // assume both can takeover one another
    x = find_par(x);
    y = find_par(y);

    if (x == y) {return;}

    if (sz_comp[x] < sz_comp[y]) {swap(x, y);} // now x is larger component, y subordinate
    sz_comp[x] += sz_comp[y];
    ptr_comp[y] = x;
    takeover[x].insert(all(takeover[y]));
    sum_comp[x] += sum_comp[y];
}

void add_town(ll town) {
    // find all neighboring active components
    vll comps;
    rep_itr(sll, itr, g[town]) {
        if (active[*itr]) {
            comps.push_back(find_par(*itr));
        }
    }

    takeover[town].insert(town);
    active[town] = true;
    sum_comp[town] = s[town];

    // find all neighbors which cannot beat town, and make them subordinate
    rep_itr(vll, itr, comps) {
        if (sum_comp[*itr] < s[town]) {
            takeover[*itr].clear();
            merge(*itr, town);
        }
    }

    // find all other neighbors which can beat town, and merge
    rep_itr(vll, itr, comps) {
        merge(*itr, town);
    }
}

int main() {
    cin >> N >> M;
    resz(s, N);
    resz(g, N);

    rep(i, 0, N) {
        cin >> s[i];
    }

    ll tempa, tempb;
    rep(i, 0, M) {
        cin >> tempa >> tempb;
        tempa--; tempb--;
        g[tempa].insert(tempb);
        g[tempb].insert(tempa);
    }

    vpll sort_s(N);
    rep(i, 0, N) {
        sort_s[i] = mp(s[i], i);
    }

    sort_all(sort_s);

    resz(ptr_comp, N);
    resz(sz_comp, N);
    resz(takeover, N);
    resz(active, N);
    resz(sum_comp, N);
    fill_n(sz_comp.begin(), N, 1);
    rep(i, 0, N) {ptr_comp[i] = i;}
    fill_n(active.begin(), N, false);
    fill_n(sum_comp.begin(), N, 0);

    rep_itr(vpll, itr, sort_s) {
        add_town(itr->second);
    }

    // consider the component of the entire island, and which tie colors can take over
    ll island = find_par(0);
    rep(i, 0, N) {
        if (takeover[island].find(i) != takeover[island].end()) {
            cout << "1";
        } else {
            cout << "0";
        }
    }

    cout << endl;

    return 0;
}

// go in order of smallest to largest town, and activate it
// if it is connected to some activated component, it can take over that component
// if it is strictly larger than the entire component, the towns that can take over that component can't take over the current town

// datastructures:
// we need component --> smaller to larger merging
// each component needs size, and set of towns capable of taking it over

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