oj.uz

답안 #719548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719548 2023-04-06T09:34:40 Z vinnipuh01 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 37296 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 ];

vector <int> v[ 400001 ];
set <pair<int, int> > st;
int used[ 400001 ];

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

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 } );
	}
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x >> y;
		v[ x ].push_back( y );
		v[ y ].push_back( x );
	}
	for ( int i = 1; i <= n; i ++ ) {
		cout << bfs( i );
		for ( int j = 1; j <= n; j ++ )
			used[ j ] = 0;
	}
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 240 ms 9980 KB Output is correct
5 Correct 211 ms 10068 KB Output is correct
6 Correct 364 ms 9992 KB Output is correct
7 Correct 249 ms 10008 KB Output is correct
8 Correct 175 ms 9980 KB Output is correct
9 Correct 316 ms 10068 KB Output is correct
10 Correct 106 ms 10056 KB Output is correct
11 Correct 108 ms 10044 KB Output is correct
12 Correct 125 ms 10068 KB Output is correct
13 Correct 188 ms 10028 KB Output is correct
14 Correct 117 ms 9940 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Execution timed out 1091 ms 37296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1066 ms 36180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1067 ms 37124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 240 ms 9980 KB Output is correct
5 Correct 211 ms 10068 KB Output is correct
6 Correct 364 ms 9992 KB Output is correct
7 Correct 249 ms 10008 KB Output is correct
8 Correct 175 ms 9980 KB Output is correct
9 Correct 316 ms 10068 KB Output is correct
10 Correct 106 ms 10056 KB Output is correct
11 Correct 108 ms 10044 KB Output is correct
12 Correct 125 ms 10068 KB Output is correct
13 Correct 188 ms 10028 KB Output is correct
14 Correct 117 ms 9940 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Execution timed out 1091 ms 37296 KB Time limit exceeded
18 Halted 0 ms 0 KB -