Submission #596679

#	Time	Username	Problem	Language	Result	Execution time	Memory
596679		Deepesson	Stranded Far From Home (BOI22_island)	C++17	100 / 100	768 ms	58120 KiB

island

#include <bits/stdc++.h>
#define MAX 205000

using ll = long long;

ll array[MAX];
ll pai[MAX];
ll size[MAX];

int find(int a){
    if(pai[a]==a)
        return a;
    return pai[a]=find(pai[a]);
}

void Union(int a,int b){
    a=find(a);
    b=find(b);
    if(a!=b){
        pai[a]=b;
        size[b]+=size[a];
        size[a]=0;
    }
}

bool answer[MAX];

typedef std::pair<ll,ll> pii;

std::map<ll,std::vector<pii>> eventos;

int main()
{
    for(int i=0;i!=MAX;++i)pai[i]=i;

    int N,M;
    std::cin>>N>>M;

    ///Corner case...
    if(N==1){
        std::cout<<"1\n";
        return 0;
    }

    for(int i=0;i!=N;++i){
        std::cin>>array[i];
        eventos[array[i]].push_back({1e9+1,i});
        size[i]=array[i];
    }

    ll soma = 0;
    for(auto&x:array)soma+=x;
    for(int i=0;i!=M;++i){
        int a,b;
        std::cin>>a>>b;--a;--b;
        int peso = std::max(array[a],array[b]);
        eventos[peso].push_back({a,b});
    }

    for(auto&x:eventos){
        std::sort(x.second.begin(),x.second.end());
        for(auto&y:x.second){
            if(y.first==1e9+1){///Consulta
                ll k = find(y.second);
                ll sum = size[k];
                ///Ve se aumentou
                if(sum!=x.first){
                    ///Sucesso
                    if(sum==soma){
                        answer[y.second]=true;
                    }else ///Ainda falta...
                    eventos[sum].push_back(y);
                }
            }else {///Unir :v
                Union(y.first,y.second);
            }
        }
    }

    for(int i=0;i!=N;++i)std::cout<<"01"[answer[i]];std::cout<<"\n";
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:80:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |     for(int i=0;i!=N;++i)std::cout<<"01"[answer[i]];std::cout<<"\n";
      |     ^~~
island.cpp:80:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |     for(int i=0;i!=N;++i)std::cout<<"01"[answer[i]];std::cout<<"\n";
      |                                                     ^~~

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