Submission #596677

#	Time	Username	Problem	Language	Result	Execution time	Memory
596677		Deepesson	Stranded Far From Home (BOI22_island)	C++17	0 / 100	2 ms	2004 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){
    //std::cout<<pai[a]<<" "<<a<<std::endl;
   // std::cout<<"bwaaaaa"<<std::endl;
    assert(a>=0);
    assert(a<=MAX);
    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];
     //   std::cout<<"Unido yey\n";
    }
}

bool answer[MAX];

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

std::vector<pii> conexao;

typedef std::pair<int,int*> pipo;

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;
    for(int i=0;i!=N;++i){std::cin>>array[i];eventos[array[i]].push_back({1e9,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});
    }
 //   std::cout<<"ok :)\n";

    for(auto&x:eventos){
        std::sort(x.second.begin(),x.second.end());
      //  std::cout<<"Checando "<<x.first<<"\n";
        for(auto&y:x.second){
            if(y.first==1e9){///Consulta
              //  std::cout<<"Pesquisa :)\n"<<std::endl;
                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...
                //    std::cout<<"Uh adicionou lul\n";
                    eventos[sum].push_back(y);
                }
            }else {
              //  std::cout<<"Une!!! "<<y.first<<" "<<y.second<<"\n";
                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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35