oj.uz

Submission #830315

# Submission time Handle Problem Language Result Execution time Memory
830315 2023-08-19T03:13:40 Z Warinchai Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 14888 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);
    }
    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 3 ms 5076 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 148 ms 5140 KB Output is correct
5 Correct 138 ms 5044 KB Output is correct
6 Correct 205 ms 5124 KB Output is correct
7 Correct 146 ms 5132 KB Output is correct
8 Correct 118 ms 5048 KB Output is correct
9 Correct 212 ms 5160 KB Output is correct
10 Correct 58 ms 5140 KB Output is correct
11 Correct 49 ms 5076 KB Output is correct
12 Correct 56 ms 5140 KB Output is correct
13 Correct 96 ms 5128 KB Output is correct
14 Correct 87 ms 5124 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 3 ms 5076 KB Output is correct
3 Execution timed out 1083 ms 14888 KB Time limit exceeded
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 Execution timed out 1079 ms 13644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5028 KB Output is correct
2 Execution timed out 1067 ms 14076 KB Time limit exceeded
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 3 ms 5076 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 148 ms 5140 KB Output is correct
5 Correct 138 ms 5044 KB Output is correct
6 Correct 205 ms 5124 KB Output is correct
7 Correct 146 ms 5132 KB Output is correct
8 Correct 118 ms 5048 KB Output is correct
9 Correct 212 ms 5160 KB Output is correct
10 Correct 58 ms 5140 KB Output is correct
11 Correct 49 ms 5076 KB Output is correct
12 Correct 56 ms 5140 KB Output is correct
13 Correct 96 ms 5128 KB Output is correct
14 Correct 87 ms 5124 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Execution timed out 1083 ms 14888 KB Time limit exceeded
18 Halted 0 ms 0 KB -