oj.uz

답안 #711433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711433 2023-03-17T01:27:08 Z Karpin Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 47812 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];

unordered_set<ll> usedNodes;

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){
    ll parMy = findPar(node).first;
    if (sizeOfWeightsSumInOneComponent[parMy] < weightsByOne[min((ll) weightsByOne.size() - 1,  weightsByOnePoll + 1)]){
        canWin[parMy] = false;
    }
}

void process(ll node){
    allHeads.insert(node);
    usedNodes.insert(node);
    for(ll j : lines[node]){
        if (usedNodes.find(j) != usedNodes.end()){
            ll parJ = findPar(j).first;
            ll parMy = findPar(node).first;
            if (parJ == parMy) continue;
            if (weights[parMy] > weights[parJ]){
                head[parJ] = parMy;
                allHeads.erase(parJ);
                // sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parMy] += sizeOfWeightsSumInOneComponent[parJ];
            }else if (weights[parMy] == weights[parJ]) {
                head[parMy] = parJ;
                allHeads.erase(parMy);
                // sizeOfComponent[parMy] += sizeOfComponent[parJ];
                sizeOfWeightsSumInOneComponent[parJ] += sizeOfWeightsSumInOneComponent[parMy];
            }

        }
    }
    
}



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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 6 ms 724 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 704 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 9 ms 824 KB Output is correct
11 Correct 10 ms 724 KB Output is correct
12 Correct 8 ms 744 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 3 ms 724 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 299 ms 47812 KB Output is correct
4 Correct 268 ms 37264 KB Output is correct
5 Execution timed out 1080 ms 38572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1046 ms 37960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 433 ms 38660 KB Output is correct
3 Correct 431 ms 42964 KB Output is correct
4 Correct 479 ms 43216 KB Output is correct
5 Correct 430 ms 43092 KB Output is correct
6 Correct 380 ms 41684 KB Output is correct
7 Correct 253 ms 47608 KB Output is correct
8 Correct 135 ms 41260 KB Output is correct
9 Correct 235 ms 23460 KB Output is correct
10 Correct 369 ms 41684 KB Output is correct
11 Correct 333 ms 40820 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 6 ms 724 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 704 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 9 ms 824 KB Output is correct
11 Correct 10 ms 724 KB Output is correct
12 Correct 8 ms 744 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 299 ms 47812 KB Output is correct
18 Correct 268 ms 37264 KB Output is correct
19 Execution timed out 1080 ms 38572 KB Time limit exceeded
20 Halted 0 ms 0 KB -