Submission #711050

#	Time	Username	Problem	Language	Result	Execution time	Memory
711050		zyq_	Stranded Far From Home (BOI22_island)	C++17	0 / 100	306 ms	80504 KiB

island

#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=0;
    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;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35