oj.uz

Submission #603977

# Submission time Handle Problem Language Result Execution time Memory
603977 2022-07-24T14:22:31 Z Ahmadsm2005 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 15784 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;
            return;
        }
        else if(R[edges[X][i]] == 1 && V[edges[X][i]] == V[X]){
            R[X] = 1;
            return;
        }
    }
    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;
        CNT = min(CNT,(int)1e9);
        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(int)':
island.cpp:8:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i = 0; i < edges[X].size(); i += 1){
      |                    ~~^~~~~~~~~~~~~~~~~
island.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i = 0; i < edges[F].size(); i += 1){
      |                        ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 5 ms 4948 KB Output is correct
3 Correct 5 ms 5020 KB Output is correct
4 Correct 344 ms 5100 KB Output is correct
5 Correct 415 ms 5108 KB Output is correct
6 Correct 234 ms 5096 KB Output is correct
7 Correct 408 ms 5104 KB Output is correct
8 Correct 267 ms 5092 KB Output is correct
9 Correct 281 ms 5136 KB Output is correct
10 Correct 169 ms 5104 KB Output is correct
11 Correct 154 ms 5100 KB Output is correct
12 Correct 153 ms 5104 KB Output is correct
13 Correct 4 ms 5148 KB Output is correct
14 Correct 148 ms 5104 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1091 ms 13468 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 1094 ms 13692 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 5 ms 4948 KB Output is correct
3 Correct 5 ms 5020 KB Output is correct
4 Correct 344 ms 5100 KB Output is correct
5 Correct 415 ms 5108 KB Output is correct
6 Correct 234 ms 5096 KB Output is correct
7 Correct 408 ms 5104 KB Output is correct
8 Correct 267 ms 5092 KB Output is correct
9 Correct 281 ms 5136 KB Output is correct
10 Correct 169 ms 5104 KB Output is correct
11 Correct 154 ms 5100 KB Output is correct
12 Correct 153 ms 5104 KB Output is correct
13 Correct 4 ms 5148 KB Output is correct
14 Correct 148 ms 5104 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Execution timed out 1092 ms 15784 KB Time limit exceeded
18 Halted 0 ms 0 KB -