oj.uz

Submission #719573

# Submission time Handle Problem Language Result Execution time Memory
719573 2023-04-06T09:59:41 Z vinnipuh01 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 36188 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 ] && to > 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 234 ms 9992 KB Output is correct
5 Correct 205 ms 10040 KB Output is correct
6 Correct 345 ms 9984 KB Output is correct
7 Correct 228 ms 9940 KB Output is correct
8 Correct 174 ms 9952 KB Output is correct
9 Correct 306 ms 10032 KB Output is correct
10 Correct 106 ms 10016 KB Output is correct
11 Correct 100 ms 10016 KB Output is correct
12 Correct 119 ms 9940 KB Output is correct
13 Correct 187 ms 10148 KB Output is correct
14 Correct 115 ms 10036 KB Output is correct

Subtask #2
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 Incorrect 158 ms 35684 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 1090 ms 36188 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 164 ms 35604 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 234 ms 9992 KB Output is correct
5 Correct 205 ms 10040 KB Output is correct
6 Correct 345 ms 9984 KB Output is correct
7 Correct 228 ms 9940 KB Output is correct
8 Correct 174 ms 9952 KB Output is correct
9 Correct 306 ms 10032 KB Output is correct
10 Correct 106 ms 10016 KB Output is correct
11 Correct 100 ms 10016 KB Output is correct
12 Correct 119 ms 9940 KB Output is correct
13 Correct 187 ms 10148 KB Output is correct
14 Correct 115 ms 10036 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Incorrect 158 ms 35684 KB Output isn't correct
18 Halted 0 ms 0 KB -