oj.uz

Submission #711046

# Submission time Handle Problem Language Result Execution time Memory
711046 2023-03-16T07:37:24 Z zyq_ Stranded Far From Home (BOI22_island) C++17
0 / 100
 321 ms 81164 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, M, inp, inp2;
deque<pair<int, int> > d;
vector<int> adjList[200010];
int added[200010];
int P[200010];
int sz[200010];
int num[200100];
int ans;
int numdel[200010];
bool flick[200010];
vector<int> s[200010];
vector<int> rmd[200010];

int find(int x){
    return (P[x] == x ? x : P[x] = find(P[x]));
}
bool same(int x, int y){
    return find(x) == find(y);
}

int32_t main(){
    cin >> N >> M;
    deque<pair<int, int> > c;
    for(int a=0; a<N; a++){
        cin >> inp;
        d.push_back({inp, a+1});
    }
    c = d;
    sort(d.begin(), d.end());
    for(int a=0; a<M; a++){
        cin >> inp >> inp2;
        adjList[inp].push_back(inp2);
        adjList[inp2].push_back(inp);
    }
    //some kind of ufds that stores num of deleted kids, total sum
    for(int a=1; a<=N; a++){
        P[a] = a;
        sz[a] = c[a-1].first;
        num[a] = 1;
        s[a].push_back(a);
    }
    //for(auto it: d){
     //   cout << it.first << ' ' << it.second << '\n';
    //}
    //cout << "hello its over \n\n";
    int las;
    while(!d.empty()){
        int cursz = d[0].first;
        while(!d.empty() && d[0].first == cursz){
            las = d[0].second;
            auto it = d[0];
            d.pop_front();
            //ins d[0]
            added[it.second] = true;
            for(auto e: adjList[it.second]){
                if(added[e] && !same(e, it.second)){
                    //cout << it.second << " and " << e << " falls under: case ";
                    e = find(e);
                    if(sz[e] < it.first){
                        //cout << "1\n";
                        //cout << "thus ans from: " << ans << " to ";
                        ans -= numdel[e];
                        ans += num[e];
                        //add s[e] to rmd[it.second] and s[it.second]
                        //cout << ans << '\n';
                        vector<int> t = s[e];
                        if((int)s[e].size() > (int)s[it.second].size()) swap(s[e], s[it.second]);
                        for(auto itt: s[e]) s[it.second].push_back(itt);
                        if((int)t.size() > (int)rmd[it.second].size()) swap(t, rmd[it.second]);
                        for(auto itt: t) rmd[it.second].push_back(itt);
                        P[e] = it.second;
                        numdel[it.second] += num[e];
                        num[it.second] += num[e];
                        sz[it.second] += sz[e];
                    }
                    else{
                        //cout << "2\n";
                        //can do 
                        numdel[it.first] += numdel[e];
                        num[it.second] += num[e];
                        P[e] = it.second;
                        sz[it.second] += sz[e];
                        //add rmd to rmd and s to s
                        if((int)s[e].size() > (int)s[it.second].size()) swap(s[e], s[it.second]);
                        for(auto itt: s[e]) s[it.second].push_back(itt);
                        if((int)rmd[e].size() > (int)rmd[it.second].size()) swap(rmd[e], rmd[it.second]);
                        for(auto itt: rmd[e]) rmd[it.second].push_back(itt);
                    }
                }
            }
        }
    }
    
    for(auto it: rmd[las]){
        flick[it] = true;
    }
    for(int a=1; a<=N; a++){
        if(flick[a]) cout << 0;
        else cout << 1;
    }
}

Compilation message

island.cpp: In function 'int32_t main()':
island.cpp:50:9: warning: 'las' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     int las;
      |         ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14432 KB Output is correct
2 Correct 9 ms 14328 KB Output is correct
3 Correct 11 ms 14316 KB Output is correct
4 Runtime error 26 ms 29560 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 8 ms 14328 KB Output is correct
3 Runtime error 287 ms 80188 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14396 KB Output is correct
2 Runtime error 312 ms 81164 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14396 KB Output is correct
2 Runtime error 321 ms 79652 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14432 KB Output is correct
2 Correct 9 ms 14328 KB Output is correct
3 Correct 11 ms 14316 KB Output is correct
4 Runtime error 26 ms 29560 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -