Submission #711460

#	Time	Username	Problem	Language	Result	Execution time	Memory
711460		Karpin	Stranded Far From Home (BOI22_island)	C++14	40 / 100	1091 ms	32468 KiB

island

#include <bits/stdc++.h>
#include <fstream>

using namespace std;


#define ll long long
#define vt vector
#define ar array

ifstream cinn ("in.txt");
ofstream coutt ("myout.txt");

const ll maxn = 200005;

ll weights[maxn];

ll n, m;

unordered_map<ll, vt<ll>> lines;

ll head[maxn];

bool usedNodes[maxn];

unordered_set<ll> usedWeights;

vt<ll> weightsByOne;

vt<pair<ll, ll>> allWeights;

ll sizeOfWeightsSumInOneComponent[maxn];
// ll sizeOfComponent[maxn];

bool canWin[maxn];

ll weightsByOnePoll = 0;

vt<int> allHeads;

bool notHeadAnymore[maxn];

bool willBeHead[maxn];

ll mymax = 0;


pair<ll, bool> findPar(ll node){
    if (head[node] != node) {

        pair<ll, bool> mypair = findPar(head[node]);
        head[node] = mypair.first;
        canWin[node] = canWin[node] && mypair.second;
    }
    return {head[node], canWin[node]};
}

void checkIfFits(ll node){
    int node1 = findPar(node).first;
    if (sizeOfWeightsSumInOneComponent[node1] < weightsByOne[min((ll) weightsByOne.size() - 1,  weightsByOnePoll + 1)]){
        canWin[node1] = false;
    }
}

void process(ll node){
    usedNodes[node] = true;
    for(ll j : lines[node]){
        if (usedNodes[j]){
            ll parJ = findPar(j).first;
            ll parMy = findPar(node).first;
            if (parJ == parMy) continue;
            if (weights[parMy] > weights[parJ]){
                head[parJ] = parMy;
                notHeadAnymore[parJ] = true;
                // if (allHeads.find(parJ) != allHeads.end())
                //     allHeads.erase(parJ);
                // sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parMy] += sizeOfWeightsSumInOneComponent[parJ];
                sizeOfWeightsSumInOneComponent[parMy] = min(sizeOfWeightsSumInOneComponent[parMy], mymax + 1);
                if (sizeOfWeightsSumInOneComponent[parMy] >= mymax) willBeHead[parMy] = true;
            }else if (weights[parMy] == weights[parJ]) {
                head[parMy] = parJ;
                notHeadAnymore[parMy] = true;
                // if (allHeads.find(parMy) != allHeads.end())
                //     allHeads.erase(parMy);
                // sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parJ] += sizeOfWeightsSumInOneComponent[parMy];
                sizeOfWeightsSumInOneComponent[parJ] = min(sizeOfWeightsSumInOneComponent[parJ], mymax + 1);
                if (sizeOfWeightsSumInOneComponent[parJ] >= mymax) willBeHead[parJ] = true;
            }

        }
    }
    if (head[node] == node) allHeads.push_back(node);
    
}



void solve(){
		
    cin >> n >> m;
    for (ll i = 0; i < n; i++){
        ll w;
        cin >> w;
        mymax = max(mymax, w);
        weights[i + 1] = w;
        if (usedWeights.find(w) == usedWeights.end()) {
            usedWeights.insert(w);
            weightsByOne.push_back(w);
        }
        allWeights.push_back({w, i + 1});

    }

    for (ll i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;

        if (weights[a] > weights[b]){
            if (lines.find(a) == lines.end()) lines[a] = {};
            lines[a].push_back(b);
        }else if (weights[b] > weights[a]){
            if (lines.find(b) == lines.end()) lines[b] = {};
            lines[b].push_back(a);
        }else{
            if (lines.find(a) == lines.end()) lines[a] = {};
            lines[a].push_back(b);
            if (lines.find(b) == lines.end()) lines[b] = {};
            lines[b].push_back(a);
        }

     

    }

    for (ll i = 0; i < n; i++){
        head[i + 1] = i + 1;
        sizeOfWeightsSumInOneComponent[i + 1] = weights[i + 1];
        // sizeOfComponent[i + 1] = 1;
        canWin[i + 1] = true;
        
    }


    sort(allWeights.begin(), allWeights.end());
    sort(weightsByOne.begin(), weightsByOne.end());



    for (ll i = 0; i < n; i++){
        if (allWeights[i].first > weightsByOne[weightsByOnePoll]) {
            for (int it = 0; it < allHeads.size(); it++){
                if (notHeadAnymore[allHeads[it]]) continue;
                if (willBeHead[allHeads[it]]) continue;
                checkIfFits(allHeads[it]);
            }

            
            weightsByOnePoll++;
        }

        process(allWeights[i].second);
    }


    string res = "";

    for (ll i = 1; i <= n; i++){
        findPar(i);
    }

    for (ll i = 1; i <= n; i++)
        res += canWin[i] ? "1" : "0";


    cout << res << endl;





}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);
	
	ll testcases = 1;

    

	// cin >> testcases;

	while(testcases--){
		solve();
	}

	return 0;

}

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:153:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for (int it = 0; it < allHeads.size(); it++){
      |                              ~~~^~~~~~~~~~~~~~~~~

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