oj.uz

Submission #596677

# Submission time Handle Problem Language Result Execution time Memory
596677 2022-07-15T00:48:23 Z Deepesson Stranded Far From Home (BOI22_island) C++17
0 / 100
 2 ms 2004 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1924 KB Output is correct
3 Incorrect 1 ms 2004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Incorrect 1 ms 1876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1924 KB Output is correct
3 Incorrect 1 ms 2004 KB Output isn't correct
4 Halted 0 ms 0 KB -