oj.uz

Submission #719716

# Submission time Handle Problem Language Result Execution time Memory
719716 2023-04-06T14:15:00 Z vinnipuh01 Stranded Far From Home (BOI22_island) C++17
20 / 100
 375 ms 52084 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 ) {
		return 0;
		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 5 ms 9684 KB Output is correct
4 Correct 233 ms 9964 KB Output is correct
5 Correct 214 ms 10128 KB Output is correct
6 Correct 375 ms 9964 KB Output is correct
7 Correct 229 ms 9940 KB Output is correct
8 Correct 177 ms 9920 KB Output is correct
9 Correct 341 ms 10012 KB Output is correct
10 Correct 111 ms 9984 KB Output is correct
11 Correct 113 ms 9940 KB Output is correct
12 Correct 126 ms 10008 KB Output is correct
13 Correct 211 ms 9940 KB Output is correct
14 Correct 116 ms 9940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 196 ms 43692 KB Output is correct
4 Correct 207 ms 42280 KB Output is correct
5 Correct 222 ms 36700 KB Output is correct
6 Correct 222 ms 37504 KB Output is correct
7 Correct 248 ms 37480 KB Output is correct
8 Correct 222 ms 37676 KB Output is correct
9 Correct 189 ms 38436 KB Output is correct
10 Correct 165 ms 36536 KB Output is correct
11 Correct 159 ms 39696 KB Output is correct
12 Correct 208 ms 36284 KB Output is correct
13 Correct 173 ms 50636 KB Output is correct
14 Correct 221 ms 50756 KB Output is correct
15 Correct 191 ms 52084 KB Output is correct
16 Correct 138 ms 51720 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 Incorrect 264 ms 33068 KB Output isn't correct
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 196 ms 34116 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 5 ms 9684 KB Output is correct
4 Correct 233 ms 9964 KB Output is correct
5 Correct 214 ms 10128 KB Output is correct
6 Correct 375 ms 9964 KB Output is correct
7 Correct 229 ms 9940 KB Output is correct
8 Correct 177 ms 9920 KB Output is correct
9 Correct 341 ms 10012 KB Output is correct
10 Correct 111 ms 9984 KB Output is correct
11 Correct 113 ms 9940 KB Output is correct
12 Correct 126 ms 10008 KB Output is correct
13 Correct 211 ms 9940 KB Output is correct
14 Correct 116 ms 9940 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 196 ms 43692 KB Output is correct
18 Correct 207 ms 42280 KB Output is correct
19 Correct 222 ms 36700 KB Output is correct
20 Correct 222 ms 37504 KB Output is correct
21 Correct 248 ms 37480 KB Output is correct
22 Correct 222 ms 37676 KB Output is correct
23 Correct 189 ms 38436 KB Output is correct
24 Correct 165 ms 36536 KB Output is correct
25 Correct 159 ms 39696 KB Output is correct
26 Correct 208 ms 36284 KB Output is correct
27 Correct 173 ms 50636 KB Output is correct
28 Correct 221 ms 50756 KB Output is correct
29 Correct 191 ms 52084 KB Output is correct
30 Correct 138 ms 51720 KB Output is correct
31 Correct 5 ms 9684 KB Output is correct
32 Incorrect 264 ms 33068 KB Output isn't correct
33 Halted 0 ms 0 KB -