oj.uz

Submission #711420

# Submission time Handle Problem Language Result Execution time Memory
711420 2023-03-16T22:10:20 Z Karpin Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 51784 KB 
#include <bits/stdc++.h>

using namespace std;


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

const ll maxn = 200005;

ll weights[maxn];

int n, m;

unordered_map<int, vt<int>> lines;

int head[maxn];

unordered_set<int> usedNodes;

unordered_set<ll> usedWeights;

vt<ll> weightsByOne;

vt<pair<ll, int>> allWeights;

ll sizeOfWeightsSumInOneComponent[maxn];
int sizeOfComponent[maxn];

bool canWin[maxn];

int weightsByOnePoint = 0;


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

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

void process(int node){
    usedNodes.insert(node);
    for(int j : lines[node]){
        if (usedNodes.find(j) != usedNodes.end()){
            int parJ = findPar(j).first;
            int parMy = findPar(node).first;
            if (weights[parMy] > weights[parJ]){
                head[parJ] = parMy;
                sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parMy] += sizeOfWeightsSumInOneComponent[parJ];
            }else if (weights[parMy] == weights[parJ]) {
                head[parJ] = parMy;
                sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parMy] += sizeOfWeightsSumInOneComponent[parJ];
                canWin[parJ] = true;
            }
        }
    }
    int parMy = findPar(node).first;
    if (sizeOfWeightsSumInOneComponent[parMy] < weightsByOne[min((int) weightsByOne.size() - 1,  weightsByOnePoint + 1)]){
        canWin[parMy] = false;
    }
}



void solve(){
		
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        ll w;
        cin >> 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 (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;

        if (lines.find(a) == lines.end()) lines[a] = {};
        if (lines.find(b) == lines.end()) lines[b] = {};

        lines[a].push_back(b);
        lines[b].push_back(a);

    }

    for (int 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 (int i = 0; i < n; i++){
        if (allWeights[i].first > weightsByOne[weightsByOnePoint]) weightsByOnePoint++;
        process(allWeights[i].second);
    }

    string res = "";

    for (int i = 1; i <= n; i++){
        findPar(i);
        res += canWin[i] ? "1" : "0";
    }

    cout << res << endl;





}

int main(){

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

	// cin >> testcases;

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

	return 0;

}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Execution timed out 1085 ms 51784 KB Time limit exceeded
4 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 384 ms 51436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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