oj.uz

Submission #711468

# Submission time Handle Problem Language Result Execution time Memory
711468 2023-03-17T03:00:49 Z Karpin Stranded Far From Home (BOI22_island) C++14
0 / 100
 245 ms 26904 KB 
#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;

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 200 ms 26840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 245 ms 26904 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -