제출 #711467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711467		Karpin	Stranded Far From Home (BOI22_island)	C++14	40 / 100	1086 ms	32856 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<pair<ll, ll>> allWeights;

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

bool canWin[maxn];


vt<int> allHeads;

bool notHeadAnymore[maxn];

bool willBeHead[maxn];

ll mymax = 0;

bool wasInLines[maxn];


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, ll gaga){
    int node1 = findPar(node).first;
    if (sizeOfWeightsSumInOneComponent[node1] < gaga){
        canWin[node1] = true;
    }
}

void process(ll node){
    ll parMy = findPar(node).first;
    usedNodes[node] = true;
    for(ll j : lines[node]){
        if (usedNodes[j]){
            ll parJ = findPar(j).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;
                parMy = head[parMy];
            }

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

        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 (!wasInLines[a]) {
                lines[a] = {};
                wasInLines[a] = true;
            }
            lines[a].push_back(b);
        }else if (weights[b] > weights[a]){
            if (!wasInLines[b]) {
                lines[b] = {};
                wasInLines[b] = true;
            }
            lines[b].push_back(a);
        }else{
            if (!wasInLines[a]) {
                lines[a] = {};
                wasInLines[a] = true;
            }
            lines[a].push_back(b);
            if (!wasInLines[b]) {
                lines[b] = {};
                wasInLines[b] = true;
            }
            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());



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

            
        }

        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;

}

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

island.cpp: In function 'void solve()':
island.cpp:164:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             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