oj.uz

Submission #719715

# Submission time Handle Problem Language Result Execution time Memory
719715 2023-04-06T14:14:32 Z vinnipuh01 Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 54476 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 ];

struct Node {
	int mx, i;
	
	Node operator + ( Node a ) {
		Node c;
		if ( mx > a.mx )
			c.mx = mx, c.i = i;
		else
			c = a;
		return c;
	}
} t[ 400001 ], anss;

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 ];
		}
	}
}

void build( int v, int tl, int tr ) {
	if ( tl == tr ) {
		t[ v ].mx = a[ tl ];
		t[ v ].i = tl;
		return;
	}
	int mid = ( tl + tr ) / 2;
	build( v + v, tl, mid );
	build( v + v + 1, mid + 1, tr );
	t[ v  ] = t[ v + v ] + t[ v + v + 1 ];
}

void gett( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		anss = anss + t[ v ];
		return;
	}
	int mid = ( tl + tr ) / 2;
	gett( v + v, tl, mid, l, r );
	gett( v + v + 1, mid + 1, tr ,l ,r );
}

void calc( int num, int l, int r ) {
	if ( l > r )
		return;
	anss.mx = 0;
	anss.i = 0;
	gett( 1, 1, n, l, r );
	if ( p[ r ] - p[ l - 1 ] >= num ) {
		an[ anss.i ] = 1;
		calc( anss.mx, l, anss.i - 1 );
		calc( anss.mx, anss.i + 1, r );
	}
}

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 ] = p[ i - 1 ] + a[ i ];
		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 ) {
		calc( 0, 1, n );
		for ( int i = 1; i <= n; i ++ )
			cout << an[ i ];
		return 0;
	}
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 236 ms 9940 KB Output is correct
5 Correct 213 ms 10172 KB Output is correct
6 Correct 381 ms 9984 KB Output is correct
7 Correct 232 ms 9996 KB Output is correct
8 Correct 175 ms 9948 KB Output is correct
9 Correct 331 ms 10104 KB Output is correct
10 Correct 112 ms 10032 KB Output is correct
11 Correct 102 ms 10028 KB Output is correct
12 Correct 141 ms 10048 KB Output is correct
13 Correct 195 ms 10012 KB Output is correct
14 Correct 118 ms 10024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 252 ms 44776 KB Output is correct
4 Correct 208 ms 44620 KB Output is correct
5 Correct 267 ms 38884 KB Output is correct
6 Correct 245 ms 39728 KB Output is correct
7 Correct 251 ms 39716 KB Output is correct
8 Correct 283 ms 39904 KB Output is correct
9 Correct 202 ms 40572 KB Output is correct
10 Correct 155 ms 38856 KB Output is correct
11 Correct 167 ms 42064 KB Output is correct
12 Correct 248 ms 38520 KB Output is correct
13 Correct 200 ms 52888 KB Output is correct
14 Correct 213 ms 53112 KB Output is correct
15 Correct 236 ms 54476 KB Output is correct
16 Correct 168 ms 53984 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9696 KB Output is correct
2 Execution timed out 1047 ms 34028 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 190 ms 35036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 236 ms 9940 KB Output is correct
5 Correct 213 ms 10172 KB Output is correct
6 Correct 381 ms 9984 KB Output is correct
7 Correct 232 ms 9996 KB Output is correct
8 Correct 175 ms 9948 KB Output is correct
9 Correct 331 ms 10104 KB Output is correct
10 Correct 112 ms 10032 KB Output is correct
11 Correct 102 ms 10028 KB Output is correct
12 Correct 141 ms 10048 KB Output is correct
13 Correct 195 ms 10012 KB Output is correct
14 Correct 118 ms 10024 KB Output is correct
15 Correct 6 ms 9732 KB Output is correct
16 Correct 6 ms 9732 KB Output is correct
17 Correct 252 ms 44776 KB Output is correct
18 Correct 208 ms 44620 KB Output is correct
19 Correct 267 ms 38884 KB Output is correct
20 Correct 245 ms 39728 KB Output is correct
21 Correct 251 ms 39716 KB Output is correct
22 Correct 283 ms 39904 KB Output is correct
23 Correct 202 ms 40572 KB Output is correct
24 Correct 155 ms 38856 KB Output is correct
25 Correct 167 ms 42064 KB Output is correct
26 Correct 248 ms 38520 KB Output is correct
27 Correct 200 ms 52888 KB Output is correct
28 Correct 213 ms 53112 KB Output is correct
29 Correct 236 ms 54476 KB Output is correct
30 Correct 168 ms 53984 KB Output is correct
31 Correct 6 ms 9696 KB Output is correct
32 Execution timed out 1047 ms 34028 KB Time limit exceeded
33 Halted 0 ms 0 KB -