oj.uz

Submission #711444

# Submission time Handle Problem Language Result Execution time Memory
711444 2023-03-17T01:45:55 Z Karpin Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 39260 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<ll> weightsByOne;

vt<pair<ll, ll>> allWeights;

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

bool canWin[maxn];

ll weightsByOnePoll = 0;

unordered_set<int> allHeads;


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){
    if (sizeOfWeightsSumInOneComponent[node] < weightsByOne[min((ll) weightsByOne.size() - 1,  weightsByOnePoll + 1)]){
        canWin[node] = 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;
                if (allHeads.find(parJ) != allHeads.end())
                    allHeads.erase(parJ);
                // sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parMy] += sizeOfWeightsSumInOneComponent[parJ];
            }else if (weights[parMy] == weights[parJ]) {
                head[parMy] = parJ;
                if (allHeads.find(parMy) != allHeads.end())
                    allHeads.erase(parMy);
                // sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parJ] += sizeOfWeightsSumInOneComponent[parMy];
            }

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



void solve(){
		
    cin >> n >> m;
    for (ll 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 (ll i = 0; i < m; i++){
        ll 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 (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]) {
            unordered_set<int>::iterator it;
            for (it = allHeads.begin(); it != allHeads.end(); it++){
                checkIfFits(*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;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 676 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 7 ms 676 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 271 ms 39260 KB Output is correct
4 Correct 224 ms 28568 KB Output is correct
5 Execution timed out 1087 ms 37828 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1068 ms 37952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 299 ms 30220 KB Output is correct
3 Correct 316 ms 30272 KB Output is correct
4 Correct 307 ms 30612 KB Output is correct
5 Correct 298 ms 30276 KB Output is correct
6 Correct 278 ms 29220 KB Output is correct
7 Correct 197 ms 35964 KB Output is correct
8 Correct 112 ms 29128 KB Output is correct
9 Correct 155 ms 16776 KB Output is correct
10 Correct 267 ms 30380 KB Output is correct
11 Correct 239 ms 29384 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 676 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 7 ms 676 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 271 ms 39260 KB Output is correct
18 Correct 224 ms 28568 KB Output is correct
19 Execution timed out 1087 ms 37828 KB Time limit exceeded
20 Halted 0 ms 0 KB -