oj.uz

Submission #719566

# Submission time Handle Problem Language Result Execution time Memory
719566 2023-04-06T09:51:02 Z vinnipuh01 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 36144 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;


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

int n, m, a[ 400001 ], x, y;
int an[ 200001 ];
int p[ 400001 ], r[ 400001 ], c[ 400001 ];
int sz[ 400001 ], l[ 400001 ], sf[ 400001 ];

vector <int> v[ 400001 ];
set <pair<int, int> > st;
int used[ 400001 ];
bool ok1 = 1, ok2 = 1;
queue <int> q;

bool bfs( int u ) {
	st.clear();
	st.insert( { 0, u } );
	used[ u ] = 1;
	sum = a[ u ];
	while ( st.size() ) {
		u = st.begin()->second;
		used[ u ] = 1;
		int cost = st.begin()->first;
		st.erase( st.begin() );
		if ( sum < cost )
			return false;
		sum += cost;
		for ( auto to : v[ u ] ) {
			if ( !used[ to ] )
				st.insert( { a[ to ], to } );
		}
	}
	return true;
}

void dfs( int u, int pr = 1, int sum = 0 ) {
	sz[ u ] += a[ u ];
	for ( auto to : v[ u ] ) {
		if ( to != pr ) {
			dfs( to, u, sum );
			sz[ u ] += sz[ to ];
		}
	}
}

main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for ( int i = 1; i <= n; i ++ ) {
		cin >> a[ i ];
		p[ i ] = i;
		r[ i ] = 1;
		c[ i ] = a[ i ];
		st.insert( { a[ i ], i } );
		if ( i > 1 && a[ i ] > a[ i - 1 ] )
			ok1 = 0;
	}
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x >> y;
		v[ x ].push_back( y );
		v[ y ].push_back( x );
		if ( x > y )
			ok1 = 0;
		if ( abs( x - y ) != 1 )
			ok2 = 0;
	}
	if ( n <= 2000 ) {
		for ( int i = 1; i <= n; i ++ ) {
			cout << bfs( i );
			for ( int j = 1; j <= n; j ++ )
				used[ j ] = 0;
		}
	}
	else if ( ok1 ) {
		dfs( 1 );
		an[ 1 ] = 1;
		q.push( 1 );
		while ( q.size() ) {
			int u = q.front();
			q.pop();
			for ( auto to : v[ u ] ) {
				if ( sz[ to ] > a[ u ] ) {
					an[ to ] = 1;
					q.push( to );
				}
			}
		}
		for ( int i = 1; i <= n; i ++ )
			cout << an[ i ];
		return 0;
	}
	else if ( ok2 ) {
		l[ 1 ] = 0;
		p[ 1 ] = a[ 1 ];
		a[ 0 ] = oo;
		for ( int i = 2; i <= n; i ++ ) {
			p[ i ] = p[ i - 1 ] + a[ i ];
			l[ i ] = i - 1;
			sum = a[ i ];
			while ( a[ l[ i ] ] <= sum ) {
				sum += p[ l[ i ] ] - p[ l[ l[ i ] ] ];
				l[ i ] = l[ l[ i ] ];
			}
		}
		r[ n ] = n + 1;
		sf[ n ] = a[ n ];
		a[ n + 1 ] = oo;
		for ( int i = n - 1; i >= 1; i -- ) {
			sf[ i ] = sf[ i + 1 ] + a[ i ];
			r[ i ] = i - 1;
			sum = a[ i ];
			while ( a[ r[ i ] ] <= sum ) {
				sum += sf[ r[ i ] ] - sf[ r[ r[ i ] ] ];
				r[ i ] = r[ r[ i ] ];
			}
		} 
		
	}
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 224 ms 9940 KB Output is correct
5 Correct 215 ms 10020 KB Output is correct
6 Correct 335 ms 9976 KB Output is correct
7 Correct 246 ms 9980 KB Output is correct
8 Correct 183 ms 9952 KB Output is correct
9 Correct 289 ms 9940 KB Output is correct
10 Correct 104 ms 10016 KB Output is correct
11 Correct 101 ms 10020 KB Output is correct
12 Correct 132 ms 10040 KB Output is correct
13 Correct 191 ms 10016 KB Output is correct
14 Correct 112 ms 9940 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1070 ms 36144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 224 ms 9940 KB Output is correct
5 Correct 215 ms 10020 KB Output is correct
6 Correct 335 ms 9976 KB Output is correct
7 Correct 246 ms 9980 KB Output is correct
8 Correct 183 ms 9952 KB Output is correct
9 Correct 289 ms 9940 KB Output is correct
10 Correct 104 ms 10016 KB Output is correct
11 Correct 101 ms 10020 KB Output is correct
12 Correct 132 ms 10040 KB Output is correct
13 Correct 191 ms 10016 KB Output is correct
14 Correct 112 ms 9940 KB Output is correct
15 Correct 5 ms 9648 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Incorrect 163 ms 35708 KB Output isn't correct
18 Halted 0 ms 0 KB -