oj.uz

Submission #603971

# Submission time Handle Problem Language Result Execution time Memory
603971 2022-07-24T14:19:33 Z Ahmadsm2005 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 21184 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N,M,V[200001],X,Y,VIS[200001];
int R[200001];
vector<int>edges[200001];
void BFS(int X){
    for(int i = 0; i < edges[X].size(); i += 1){
        if(R[edges[X][i]] == 0 && V[edges[X][i]] == V[X]){
            R[X] = 0;
        }
        else if(R[edges[X][i]] == 1 && V[edges[X][i]] == V[X]){
            R[X] = 1;
        }
    }
    for(int i = 0; i < N; i += 1)VIS[i] = 0;
    priority_queue<pair<int,int>>Q;
    int CNT = V[X];
    Q.push({0,X});
    while(Q.size()){
        int F = Q.top().second,S = -Q.top().first;
        Q.pop();
        if(VIS[F])continue;
        VIS[F] = 1;
        if(S > CNT){
            R[X] = 0;
            return;
        }
        CNT += S;
        for(int i = 0; i < edges[F].size(); i += 1){
            Q.push({-V[edges[F][i]],edges[F][i]});
        }
    }
    R[X] = 1;
}
int32_t main()
{
    cin.tie(0),iostream::sync_with_stdio(0);
    cin>>N>>M;
    for(int i = 0; i < N; i += 1){
        cin>>V[i];
        R[i] = -1;
    }
    for(int i = 0; i < M; i += 1){
        cin>>X>>Y;
        edges[X - 1].push_back(Y - 1),edges[Y - 1].push_back(X - 1);
    }
    for(int i = 0; i < N; i += 1){
        BFS(i);
    }
    for(int i = 0; i < N; i += 1)cout<<R[i];
}

Compilation message

island.cpp: In function 'void BFS(long long int)':
island.cpp:8:22: 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]
    8 |     for(int i = 0; i < edges[X].size(); i += 1){
      |                    ~~^~~~~~~~~~~~~~~~~
island.cpp:30:26: 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]
   30 |         for(int i = 0; i < edges[F].size(); i += 1){
      |                        ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 361 ms 5172 KB Output is correct
5 Correct 303 ms 5156 KB Output is correct
6 Correct 568 ms 5188 KB Output is correct
7 Correct 348 ms 5076 KB Output is correct
8 Correct 285 ms 5168 KB Output is correct
9 Correct 478 ms 5228 KB Output is correct
10 Correct 154 ms 5160 KB Output is correct
11 Correct 172 ms 5168 KB Output is correct
12 Correct 140 ms 5204 KB Output is correct
13 Correct 357 ms 5216 KB Output is correct
14 Correct 230 ms 5164 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1076 ms 17416 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 361 ms 5172 KB Output is correct
5 Correct 303 ms 5156 KB Output is correct
6 Correct 568 ms 5188 KB Output is correct
7 Correct 348 ms 5076 KB Output is correct
8 Correct 285 ms 5168 KB Output is correct
9 Correct 478 ms 5228 KB Output is correct
10 Correct 154 ms 5160 KB Output is correct
11 Correct 172 ms 5168 KB Output is correct
12 Correct 140 ms 5204 KB Output is correct
13 Correct 357 ms 5216 KB Output is correct
14 Correct 230 ms 5164 KB Output is correct
15 Correct 5 ms 5040 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 1077 ms 21184 KB Time limit exceeded
18 Halted 0 ms 0 KB -