oj.uz

Submission #603482

# Submission time Handle Problem Language Result Execution time Memory
603482 2022-07-24T07:31:19 Z almothana05 Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 27824 KB 
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
queue<long long>q;
priority_queue<pair<long long, long long> >pri;
vector<long long>gr[200000];
long long num[200000] , vis[200000];
int main(){
    long long menge , numm = 0, nummer  , ed;
    cin >> menge >> ed;
    for(long long i = 0 ;i < menge ; i++){
        cin >> numm;
        num[i + 1] = numm;
    }
    for(long long i = 0 ; i< ed ; i++){
        cin >> numm >> nummer;
        gr[numm].push_back(nummer);
        gr[nummer].push_back(numm);
    }
    for(long long i = 1 ; i <= menge ; i++){
        long long fl = 1;
        long long cmp = 0;
        vis[i] = 1;
        q.push(i);
        while(q.size()){
            long long jet = q.front();
            q.pop();
            cmp += num[jet];
            for(long long i = 0 ; i < gr[jet].size() ; i++){
                long long kind = gr[jet][i];
                pri.push({-num[kind] , kind });
            }
            while(pri.size() && -pri.top().first <= cmp){
                if(vis[pri.top().second] == 0){
                    vis[pri.top().second] = 1;
                    q.push(pri.top().second);
                }
                pri.pop();
            }
        }
        while(pri.size()){
            pri.pop();
        }
        for(long long j = 1 ; j <=menge ; j++){
            if(vis[j] == 0){
                fl = 0;
            }
            vis[j] = 0;
        }
        cout << fl ;
    }
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:29:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             for(long long i = 0 ; i < gr[jet].size() ; i++){
      |                                   ~~^~~~~~~~~~~~~~~~

Subtask #1
10.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 Correct 3 ms 4948 KB Output is correct
4 Correct 133 ms 5196 KB Output is correct
5 Correct 133 ms 5124 KB Output is correct
6 Correct 206 ms 5188 KB Output is correct
7 Correct 127 ms 5076 KB Output is correct
8 Correct 98 ms 5108 KB Output is correct
9 Correct 343 ms 5148 KB Output is correct
10 Correct 132 ms 5124 KB Output is correct
11 Correct 119 ms 5120 KB Output is correct
12 Correct 96 ms 5152 KB Output is correct
13 Correct 217 ms 5100 KB Output is correct
14 Correct 107 ms 5012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4892 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Runtime error 245 ms 27824 KB Execution killed with signal 11
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 1085 ms 14300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Execution timed out 1090 ms 15384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 Correct 3 ms 4948 KB Output is correct
4 Correct 133 ms 5196 KB Output is correct
5 Correct 133 ms 5124 KB Output is correct
6 Correct 206 ms 5188 KB Output is correct
7 Correct 127 ms 5076 KB Output is correct
8 Correct 98 ms 5108 KB Output is correct
9 Correct 343 ms 5148 KB Output is correct
10 Correct 132 ms 5124 KB Output is correct
11 Correct 119 ms 5120 KB Output is correct
12 Correct 96 ms 5152 KB Output is correct
13 Correct 217 ms 5100 KB Output is correct
14 Correct 107 ms 5012 KB Output is correct
15 Correct 3 ms 4892 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Runtime error 245 ms 27824 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -