oj.uz

Submission #711460

# Submission time Handle Problem Language Result Execution time Memory
711460 2023-03-17T02:25:38 Z Karpin Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 32468 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;

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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 7 ms 596 KB Output is correct
5 Correct 8 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 10 ms 712 KB Output is correct
12 Correct 6 ms 664 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 1 ms 340 KB Output is correct
3 Execution timed out 1091 ms 32220 KB Time limit exceeded
4 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 1073 ms 31548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 215 ms 26784 KB Output is correct
3 Correct 227 ms 26708 KB Output is correct
4 Correct 233 ms 26868 KB Output is correct
5 Correct 265 ms 29448 KB Output is correct
6 Correct 241 ms 28176 KB Output is correct
7 Correct 155 ms 32468 KB Output is correct
8 Correct 99 ms 27720 KB Output is correct
9 Correct 130 ms 14996 KB Output is correct
10 Correct 241 ms 29144 KB Output is correct
11 Correct 193 ms 26768 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 7 ms 596 KB Output is correct
5 Correct 8 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 10 ms 712 KB Output is correct
12 Correct 6 ms 664 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 1 ms 340 KB Output is correct
17 Execution timed out 1091 ms 32220 KB Time limit exceeded
18 Halted 0 ms 0 KB -