oj.uz

Submission #879438

# Submission time Handle Problem Language Result Execution time Memory
879438 2023-11-27T12:23:03 Z vladburac Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 21012 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int NMAX = 2e5;

pair<int, int> v[NMAX+1];
vector <int> edges[NMAX+1];
int parent[NMAX+1];
bool viz[NMAX+1];
int marked[NMAX+1];
ll sum[NMAX+1];

pair<int, bool> findd( int x ) { // parintele si daca am marcat pe lant pana la radacina
  if( parent[x] == x )
    return { x, marked[x] };
  pair<int, bool> y = findd( parent[x] );
  return { y.first, y.second | marked[y.first] };
}

void unite( int a, int b ) {
  int x = findd( a ).first;
  int y = findd( b ).first;
  if( x != y ) {
    parent[x] = y;
    sum[y] += sum[x];
  }
}
void solve() {
  int n, m, i, a, b;
  cin >> n >> m;
  for( i = 0; i < n; i++ ) {
    cin >> v[i].first;
    v[i].second = i;
    parent[i] = i;
    viz[i] = false;
    sum[i] = v[i].first;
  }
  v[n].first = 0;
  for( i = 0; i < m; i++ ) {
    cin >> a >> b;
    a--, b--;
    edges[a].push_back( b );
    edges[b].push_back( a );
  }
  sort( v, v + n );
  for( i = 0; i < n; i++ ) {
    viz[v[i].second] = true;
    for( auto vec: edges[v[i].second] ) {
      if( viz[vec] )
        unite( v[i].second, vec );
    }
    int comp = findd( v[i].second ).first;
    if( sum[comp] < v[i+1].first )
      marked[comp] = true;
  }
  for( i = 0; i < n; i++ )
    a = findd( i ).first;
  for( i = 0; i < n; i++ )
    cout << 1 - marked[i];
  cout << "\n";
}
int main() {
  //ios_base::sync_with_stdio( false );
  //cin.tie( NULL );
  //cout.tie( NULL );
  int t = 1;
  //cin >> t;
  while( t-- )
    solve();
  return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Execution timed out 1079 ms 21012 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 278 ms 20856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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