oj.uz

Submission #993748

# Submission time Handle Problem Language Result Execution time Memory
993748 2024-06-06T11:06:27 Z MarwenElarbi Stranded Far From Home (BOI22_island) C++17
10 / 100
 210 ms 45904 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
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];
}
void build(int x){
  vis[x]=true;
  for(auto u:adj[x]){
    if(vis[u]) continue;
    newadj[x].pb(u);
    newadj[u].pb(x);
    build(u);
  }
  return;
}
void dfs(int x,int p){
  sz[x]=tab[x];
  //cout <<x<<" "<<p<<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 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Incorrect 5 ms 9884 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 4 ms 9780 KB Output is correct
3 Correct 193 ms 34720 KB Output is correct
4 Correct 168 ms 34512 KB Output is correct
5 Correct 189 ms 27544 KB Output is correct
6 Correct 188 ms 27984 KB Output is correct
7 Correct 191 ms 28064 KB Output is correct
8 Correct 210 ms 30540 KB Output is correct
9 Correct 161 ms 26680 KB Output is correct
10 Correct 146 ms 24004 KB Output is correct
11 Correct 161 ms 30888 KB Output is correct
12 Correct 176 ms 28244 KB Output is correct
13 Correct 152 ms 43604 KB Output is correct
14 Correct 159 ms 43856 KB Output is correct
15 Correct 184 ms 45904 KB Output is correct
16 Correct 148 ms 44880 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 146 ms 19276 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 9816 KB Output is correct
2 Incorrect 146 ms 19324 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 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Incorrect 5 ms 9884 KB Output isn't correct
5 Halted 0 ms 0 KB -