oj.uz

Submission #719929

# Submission time Handle Problem Language Result Execution time Memory
719929 2023-04-07T04:51:24 Z vinnipuh01 Stranded Far From Home (BOI22_island) C++17
10 / 100
 563 ms 61512 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int n, m, a[ 200001 ], x, y, p[ 200001 ], r[ 200001 ], c[ 200001 ];
int an[ 200001 ];
vector <int> v[ 200001 ], v1;
vector <pair<int, pair<int, int> > > vv;
map <int, vector <int> > mp;
set <int> st, stt;

int fin( int a ) {
	if ( p[ a ] == a )
		return a;
	return p[ a ] = fin( p[ a ] );
}

void unin( int a, int b ) {
	a = fin( a );
	b = fin( b );
	if ( a == b )
		return;
	if ( r[ a ] < r[ b ] )
		swap( a, b );
	r[  a] += r[ b ];
	c[ a ] += c[ b ];
	p[ b ] = a;
}

void dfs( int u ) {
	an[ u ] = 0;
	for ( auto to : v[ u ] ) {
		if ( an[ to ] )
			dfs( to );
	}
}

main () {
	cin >> n >> m;
	for ( int i = 1; i <= n; i ++ ) {
		cin >> a[ i ]; 
		an[ i ] = 1;
		p[ i ] = i;
		r[ i ] = 1;
		c[ i ] = a[ i ];
		mp[ a[ i ] ].push_back( i );  
		st.insert( a[ i ] );
	}
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x >> y;
		if ( a[ x ] < a[ y ] )
			swap( x, y );
		vv.push_back( { a[ x ], make_pair( x, y ) } );
	}
	sort( vv.begin(), vv.end() );
	reverse( vv.begin(), vv.end() );
	stt = st;
	for ( auto i : st ) {
		if ( stt.size() )
			stt.erase( stt.begin() );
		if ( stt.size() )
			ans = *stt.begin();
		else
			ans = 0;
		while ( vv.size() && vv.back().first <= i ) {
			num = fin( vv.back().second.second );
			if ( c[ num ] < vv.back().first ) {
				dfs( vv.back().second.second );
			}
			v[ vv.back().second.first ].push_back( vv.back().second.second );
			v[ vv.back().second.second ].push_back( vv.back().second.first );
			unin( vv.back().second.first, vv.back().second.second );
			vv.pop_back();
		}
	}
	for ( int i = 1; i <= n; i ++ )
		cout << an[ i ];
}

Compilation message

island.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main () {
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 7 ms 5508 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 4968 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 377 ms 58672 KB Output is correct
4 Correct 216 ms 27768 KB Output is correct
5 Correct 379 ms 56708 KB Output is correct
6 Correct 383 ms 51852 KB Output is correct
7 Correct 414 ms 61364 KB Output is correct
8 Correct 279 ms 29404 KB Output is correct
9 Correct 336 ms 54076 KB Output is correct
10 Correct 304 ms 53124 KB Output is correct
11 Correct 213 ms 29648 KB Output is correct
12 Correct 256 ms 28600 KB Output is correct
13 Correct 200 ms 31068 KB Output is correct
14 Correct 203 ms 30836 KB Output is correct
15 Correct 378 ms 61512 KB Output is correct
16 Correct 340 ms 60784 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 563 ms 58300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 288 ms 26668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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