oj.uz

Submission #596678

# Submission time Handle Problem Language Result Execution time Memory
596678 2022-07-15T00:49:44 Z Deepesson Stranded Far From Home (BOI22_island) C++17
0 / 100
 2 ms 1876 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+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 {
                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:75:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   75 |     for(int i=0;i!=N;++i)std::cout<<"01"[answer[i]];std::cout<<"\n";
      |     ^~~
island.cpp:75:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |     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 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Incorrect 1 ms 1876 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 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Incorrect 1 ms 1876 KB Output isn't correct
4 Halted 0 ms 0 KB -