Submission #719579

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
719579	2023-04-06T10:04:45 Z	vinnipuh01	Stranded Far From Home (BOI22_island)	C++17	20 / 100	1000 ms	58188 KB

island

#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 ( 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	223 ms	9940 KB	Output is correct
5	Correct	201 ms	10028 KB	Output is correct
6	Correct	352 ms	9972 KB	Output is correct
7	Correct	225 ms	9980 KB	Output is correct
8	Correct	170 ms	9940 KB	Output is correct
9	Correct	292 ms	10068 KB	Output is correct
10	Correct	107 ms	10016 KB	Output is correct
11	Correct	100 ms	9948 KB	Output is correct
12	Correct	116 ms	10036 KB	Output is correct
13	Correct	187 ms	10016 KB	Output is correct
14	Correct	112 ms	10024 KB	Output is correct

Subtask #2

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	185 ms	45452 KB	Output is correct
4	Correct	182 ms	46960 KB	Output is correct
5	Correct	207 ms	42272 KB	Output is correct
6	Correct	206 ms	43332 KB	Output is correct
7	Correct	211 ms	43368 KB	Output is correct
8	Correct	241 ms	43636 KB	Output is correct
9	Correct	178 ms	44224 KB	Output is correct
10	Correct	129 ms	41696 KB	Output is correct
11	Correct	145 ms	44724 KB	Output is correct
12	Correct	191 ms	40828 KB	Output is correct
13	Correct	177 ms	55172 KB	Output is correct
14	Correct	196 ms	55460 KB	Output is correct
15	Correct	208 ms	58188 KB	Output is correct
16	Correct	135 ms	57056 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Execution timed out	1075 ms	36080 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	159 ms	35620 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	223 ms	9940 KB	Output is correct
5	Correct	201 ms	10028 KB	Output is correct
6	Correct	352 ms	9972 KB	Output is correct
7	Correct	225 ms	9980 KB	Output is correct
8	Correct	170 ms	9940 KB	Output is correct
9	Correct	292 ms	10068 KB	Output is correct
10	Correct	107 ms	10016 KB	Output is correct
11	Correct	100 ms	9948 KB	Output is correct
12	Correct	116 ms	10036 KB	Output is correct
13	Correct	187 ms	10016 KB	Output is correct
14	Correct	112 ms	10024 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	185 ms	45452 KB	Output is correct
18	Correct	182 ms	46960 KB	Output is correct
19	Correct	207 ms	42272 KB	Output is correct
20	Correct	206 ms	43332 KB	Output is correct
21	Correct	211 ms	43368 KB	Output is correct
22	Correct	241 ms	43636 KB	Output is correct
23	Correct	178 ms	44224 KB	Output is correct
24	Correct	129 ms	41696 KB	Output is correct
25	Correct	145 ms	44724 KB	Output is correct
26	Correct	191 ms	40828 KB	Output is correct
27	Correct	177 ms	55172 KB	Output is correct
28	Correct	196 ms	55460 KB	Output is correct
29	Correct	208 ms	58188 KB	Output is correct
30	Correct	135 ms	57056 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Execution timed out	1075 ms	36080 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-