oj.uz

Submission #830476

# Submission time Handle Problem Language Result Execution time Memory
830476 2023-08-19T07:03:26 Z Warinchai Stranded Far From Home (BOI22_island) C++14
10 / 100
 217 ms 12972 KB 
#include<bits/stdc++.h>
using namespace std;
long long ar[200005];
vector<int>v[200005];
int vis[200005];
int n,m;
int check(int i){
    for(int x=1;x<=n;x++){
        vis[x]=0;
    }
    priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >pq;
    pq.push({ar[i],i});
    vis[i]=1;
    long long power=0;
    int ck=0;
    while(!pq.empty()){
        long long np=pq.top().first;
        int x=pq.top().second;
        //cout<<x<<" "<<power<<endl;
        pq.pop();
        if(x==i||power>=np){
            power+=np;
            for(int j=0;j<v[x].size();j++){
                if(vis[v[x][j]]==1){
                    continue;
                }
                vis[v[x][j]]=1;
                pq.push({ar[v[x][j]],v[x][j]});
            }
        }else{
            ck=1;
            break;
        }
    }
    if(!ck){
        return 1;
    }else{
        return 0;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    if(n>2000){
        int st=1,en=n,ans=0;
        while(st>en){
            int m=(st+en)/2;
            if(check(m)){
                ans=m;
                st=m+1;
            }else{
                en=m-1;
            }
        }
        for(int i=1;i<=n;i++){
            if(i<=ans){
                cout<<1;
            }else{
                cout<<0;
            }
        }
        return 0;
    }
    for(int i=1;i<=n;i++){
        cout<<check(i);
    }
}

Compilation message

island.cpp: In function 'int check(int)':
island.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             for(int j=0;j<v[x].size();j++){
      |                         ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 152 ms 5104 KB Output is correct
5 Correct 143 ms 5100 KB Output is correct
6 Correct 213 ms 5092 KB Output is correct
7 Correct 149 ms 5096 KB Output is correct
8 Correct 104 ms 5092 KB Output is correct
9 Correct 217 ms 5076 KB Output is correct
10 Correct 56 ms 5108 KB Output is correct
11 Correct 50 ms 5100 KB Output is correct
12 Correct 48 ms 5100 KB Output is correct
13 Correct 95 ms 5096 KB Output is correct
14 Correct 88 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 152 ms 5104 KB Output is correct
5 Correct 143 ms 5100 KB Output is correct
6 Correct 213 ms 5092 KB Output is correct
7 Correct 149 ms 5096 KB Output is correct
8 Correct 104 ms 5092 KB Output is correct
9 Correct 217 ms 5076 KB Output is correct
10 Correct 56 ms 5108 KB Output is correct
11 Correct 50 ms 5100 KB Output is correct
12 Correct 48 ms 5100 KB Output is correct
13 Correct 95 ms 5096 KB Output is correct
14 Correct 88 ms 5076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Incorrect 82 ms 12972 KB Output isn't correct
18 Halted 0 ms 0 KB -