oj.uz

Submission #604178

# Submission time Handle Problem Language Result Execution time Memory
604178 2022-07-24T19:52:52 Z DanerZein Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 524288 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 pa[MAX_N];
ll sb[MAX_N];
void dfs(int u,int p){
  pa[u]=p;
  sb[u]=ha[u];
  for(auto &v:G[u]){
    if(v!=p){
      dfs(v,u);
      sb[u]+=sb[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="1";
  dfs(0,0);
  for(int i=1;i<n;i++){
    if(sb[i]>=ha[pa[i]] && ans[pa[i]]=='1') ans+='1';
    else ans+='0';
  }
  /*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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 241 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 261 ms 19832 KB Output is correct
4 Correct 205 ms 19932 KB Output is correct
5 Correct 275 ms 14880 KB Output is correct
6 Correct 264 ms 15200 KB Output is correct
7 Correct 294 ms 15256 KB Output is correct
8 Correct 270 ms 15256 KB Output is correct
9 Correct 251 ms 15236 KB Output is correct
10 Correct 194 ms 16064 KB Output is correct
11 Correct 182 ms 16064 KB Output is correct
12 Correct 245 ms 15280 KB Output is correct
13 Correct 200 ms 27584 KB Output is correct
14 Correct 225 ms 27612 KB Output is correct
15 Correct 244 ms 27704 KB Output is correct
16 Correct 190 ms 27344 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 256 ms 27188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1101 ms 289956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 241 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -