oj.uz

Submission #1099390

# Submission time Handle Problem Language Result Execution time Memory
1099390 2024-10-11T09:00:19 Z epicci23 Stranded Far From Home (BOI22_island) C++17
0 / 100
 117 ms 83188 KB 
#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5;
int s[N],par[N],val[N];
vector<int> v[N],comp[N];
bool open[N],ans[N];
priority_queue<int> pq[N];

int find(int a){
  if(par[a]==a) return a;
  return par[a]=find(par[a]);
}

void unite(int a,int b){
  a=find(a),b=find(b);
  if(a==b) return;
  if(sz(comp[a])>sz(comp[b])) swap(a,b);
  val[b]+=val[a];
  par[a]=b;
  for(int x:comp[a]) comp[b].push_back(x);
  while(!pq[a].empty()){
  	pq[b].push(pq[a].top());
  	pq[a].pop();
  }
}

void _(){
  int n,m;
  cin >> n >> m;
  iota(par,par+N,0LL);
  for(int i=1;i<=n;i++) comp[i].push_back(i);
  for(int i=1;i<=n;i++){
  	cin >> s[i];
  	val[i]+=s[i];
  }
  for(int i=1;i<=m;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }

  vector<int> lol[n+5];
  for(int i=1;i<=n;i++) lol[s[i]].push_back(i);
  for(int i=1;i<=n;i++) for(int x:v[i]) pq[i].push(-s[x]);
  
  for(int i=1;i<=n;i++){
   
    for(int u:lol[i]) open[u]=1;
    for(int u:lol[i]){
      for(int x:v[u]){
        if(!open[x]) continue;
        unite(u,x);
      }
    }
    
    vector<int> cur;
    for(int u:lol[i]) cur.push_back(find(u));
    sort(all(cur));
    cur.erase(unique(all(cur)),cur.end());
    
    for(int u:cur){
     while(!pq[u].empty() && pq[u].top()*-1<=i) pq[u].pop();
     if(pq[u].empty()){
      for(int x:comp[u]) ans[x]=1;
      comp[u].clear();
     }
     else if(pq[u].top()*-1>val[u]){
      for(int x:comp[u]) ans[x]=0;
      comp[u].clear();	
     }
    }
  }

  for(int i=1;i<=n;i++) cout << ans[i];
  cout << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 9 ms 17632 KB Output is correct
3 Correct 8 ms 17500 KB Output is correct
4 Runtime error 20 ms 35856 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17500 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Runtime error 98 ms 83188 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17500 KB Output is correct
2 Runtime error 101 ms 80892 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17496 KB Output is correct
2 Runtime error 117 ms 82880 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 9 ms 17632 KB Output is correct
3 Correct 8 ms 17500 KB Output is correct
4 Runtime error 20 ms 35856 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -