oj.uz

답안 #604154

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604154 2022-07-24T19:16:26 Z DanerZein Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 12948 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int MAX_N=2e5+10;
vector<vi> G;
int ha[MAX_N];
bool vis[MAX_N];
int n,m;
void bfs(int u){
  for(int i=0;i<n;i++) vis[i]=0;
  priority_queue<ii, vector<ii>, greater<ii> > q;
  vis[u]=1; 
  ll co=ha[u];
  for(auto &v:G[u]){
    q.push(ii(ha[v],v));
  }
  while(!q.empty()){
    int x=q.top().second; q.pop();
    if(co<ha[x]) continue;
    vis[x]=1;
    co+=ha[x];
    for(auto &v:G[x]){
      if(!vis[v]){
        q.push(ii(ha[v],v));
      }
    }
  }
}
int main(){
  cin>>n>>m;
  G.resize(n+1);
  for(int i=0;i<n;i++) cin>>ha[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 ans="";
  for(int i=0;i<n;i++){
    bfs(i);
    bool all=1;
    for(int j=0;j<n;j++) all&=vis[j];
    if(all) ans+='1';
    else ans+='0';
  }
  cout<<ans<<endl;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 218 ms 400 KB Output is correct
5 Correct 157 ms 420 KB Output is correct
6 Correct 335 ms 396 KB Output is correct
7 Correct 225 ms 340 KB Output is correct
8 Correct 177 ms 392 KB Output is correct
9 Correct 284 ms 420 KB Output is correct
10 Correct 66 ms 408 KB Output is correct
11 Correct 68 ms 412 KB Output is correct
12 Correct 67 ms 420 KB Output is correct
13 Correct 116 ms 420 KB Output is correct
14 Correct 91 ms 432 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 1093 ms 12948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1099 ms 12048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1094 ms 12264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 218 ms 400 KB Output is correct
5 Correct 157 ms 420 KB Output is correct
6 Correct 335 ms 396 KB Output is correct
7 Correct 225 ms 340 KB Output is correct
8 Correct 177 ms 392 KB Output is correct
9 Correct 284 ms 420 KB Output is correct
10 Correct 66 ms 408 KB Output is correct
11 Correct 68 ms 412 KB Output is correct
12 Correct 67 ms 420 KB Output is correct
13 Correct 116 ms 420 KB Output is correct
14 Correct 91 ms 432 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 1093 ms 12948 KB Time limit exceeded
18 Halted 0 ms 0 KB -