oj.uz

Submission #993753

# Submission time Handle Problem Language Result Execution time Memory
993753 2024-06-06T11:27:16 Z MarwenElarbi Stranded Far From Home (BOI22_island) C++17
10 / 100
 494 ms 46020 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
vector<int> newadj[nax];
bool vis[nax];
int tab[nax];
bool state[nax];
long long sz[nax];
int res[nax];
bool compare(int x,int y){
  return tab[x]>tab[y];
}
struct node{
  int child,par,x,p;
};
struct compare2{
  bool operator()(node const& p1, node const& p2)
    {
        if(p1.child!=p2.child) return p1.child < p2.child;
        else return p1.par > p2.par;
    }
};
void build(int x){
  vis[x]=true;
  priority_queue<node,vector<node>,compare2> pq;
  for(auto u:adj[x]){
    pq.push({tab[u],tab[x],u,x});
  }
  while(!pq.empty()){
    auto cur=pq.top();
    pq.pop();
    if(vis[cur.x]) continue;
    //cout <<cur.x<<" "<<cur.p<<endl;
    newadj[cur.x].pb(cur.p);
    newadj[cur.p].pb(cur.x);
    vis[cur.x]=true;
    for(auto u:adj[cur.x]){
      pq.push({tab[u],tab[cur.x],u,cur.x});
    }
  }
}
void dfs(int x,int p){
  sz[x]=tab[x];
  //cout <<newadj[x].size()<<" "<<x<<endl;
  for(auto u:newadj[x]){
    if(u==p) continue;
    dfs(u,x);
    sz[x]+=sz[u];
  }
  if(p!=-1){
    if(sz[x]>=tab[p]) state[x]=1;
    else state[x]=0;
  }
}
void ans(int x,int p){
  if(state[x]==0) return;
  res[x]=1;
  for(auto u:newadj[x]){
    if(u==p) continue;
    ans(u,x);
  }
}
int main() {
    int n,m;
    cin>>n>>m;
    pair<int,int> mx={-1,-1};
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i];
        if(mx.fi<tab[i]){
          mx={tab[i],i};
        }
    }
    for (int i = 0; i < m; ++i)
    {
      int x,y;
      cin>>x>>y;
      x--;y--;
      if(tab[x]==tab[y]){
        adj[x].pb(y);
        adj[y].pb(x);
      }else if(tab[x]>tab[y]){
        adj[x].pb(y);
      }else{
        adj[y].pb(x);
      }
    }
    for (int i = 0; i < n; ++i)
    {
      sort(adj[i].begin(),adj[i].end(),compare);
    }
    build(mx.se);
    state[mx.se]=true;
    dfs(mx.se,-1);
    ans(mx.se,-1);
    for (int i = 0; i < n; ++i)
    {
      cout <<res[i];
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9864 KB Output is correct
4 Incorrect 5 ms 9820 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 6 ms 9840 KB Output is correct
3 Correct 190 ms 34692 KB Output is correct
4 Correct 165 ms 34640 KB Output is correct
5 Correct 206 ms 27500 KB Output is correct
6 Correct 230 ms 28388 KB Output is correct
7 Correct 202 ms 28164 KB Output is correct
8 Correct 230 ms 30544 KB Output is correct
9 Correct 174 ms 26804 KB Output is correct
10 Correct 166 ms 25152 KB Output is correct
11 Correct 201 ms 31288 KB Output is correct
12 Correct 194 ms 28324 KB Output is correct
13 Correct 223 ms 43828 KB Output is correct
14 Correct 163 ms 43996 KB Output is correct
15 Correct 203 ms 46020 KB Output is correct
16 Correct 161 ms 45000 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Incorrect 494 ms 19152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Incorrect 156 ms 19284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9864 KB Output is correct
4 Incorrect 5 ms 9820 KB Output isn't correct
5 Halted 0 ms 0 KB -