oj.uz

Submission #711467

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

}

Compilation message

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.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 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 532 KB Output is correct

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 1086 ms 21716 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 1067 ms 21316 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 241 ms 26932 KB Output is correct
3 Correct 250 ms 26900 KB Output is correct
4 Correct 221 ms 27052 KB Output is correct
5 Correct 264 ms 29500 KB Output is correct
6 Correct 263 ms 28500 KB Output is correct
7 Correct 168 ms 32856 KB Output is correct
8 Correct 107 ms 27884 KB Output is correct
9 Correct 129 ms 15080 KB Output is correct
10 Correct 254 ms 29424 KB Output is correct
11 Correct 180 ms 26992 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 532 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 1086 ms 21716 KB Time limit exceeded
18 Halted 0 ms 0 KB -