oj.uz

Submission #714616

# Submission time Handle Problem Language Result Execution time Memory
714616 2023-03-25T06:40:31 Z fuad27 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 12728 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=200'010;
int s[N];
vector<int> g[N];
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for(int i = 0;i<n;i++)cin >> s[i];
  for(int i = 0;i<m;i++) {
    int a, b;
    cin >> a >> b;
    a--,b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  string res="";
  for(int i = 0;i<n;i++) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<bool> vis(n);
    long long sum=s[i];
    pq.push({0,i});
    vis[i]=1;
    bool check=true;
    while(pq.size()) {
      auto at=pq.top();
      pq.pop();
      if(at.first<=sum) {
        sum+=at.first;
      }
      else {
        check=false;
        break;
      }
      for(int to:g[at.second]) {
        if(!vis[to]){
          pq.push({s[to],to});
          vis[to]=1;
        }
      }
    }
    cout<<check;
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 170 ms 5076 KB Output is correct
5 Correct 160 ms 5076 KB Output is correct
6 Correct 199 ms 5076 KB Output is correct
7 Correct 154 ms 5076 KB Output is correct
8 Correct 120 ms 5076 KB Output is correct
9 Correct 235 ms 5088 KB Output is correct
10 Correct 78 ms 5076 KB Output is correct
11 Correct 64 ms 5076 KB Output is correct
12 Correct 60 ms 5076 KB Output is correct
13 Correct 115 ms 5076 KB Output is correct
14 Correct 91 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 4 ms 4948 KB Output is correct
3 Execution timed out 1072 ms 12728 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 1055 ms 11932 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 4948 KB Output is correct
2 Execution timed out 1078 ms 12136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 170 ms 5076 KB Output is correct
5 Correct 160 ms 5076 KB Output is correct
6 Correct 199 ms 5076 KB Output is correct
7 Correct 154 ms 5076 KB Output is correct
8 Correct 120 ms 5076 KB Output is correct
9 Correct 235 ms 5088 KB Output is correct
10 Correct 78 ms 5076 KB Output is correct
11 Correct 64 ms 5076 KB Output is correct
12 Correct 60 ms 5076 KB Output is correct
13 Correct 115 ms 5076 KB Output is correct
14 Correct 91 ms 5076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Execution timed out 1072 ms 12728 KB Time limit exceeded
18 Halted 0 ms 0 KB -