oj.uz

Submission #710907

# Submission time Handle Problem Language Result Execution time Memory
710907 2023-03-16T04:35:29 Z penguin133 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 22700 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, A[300005], m;
bool ans[300005], vis[300005];
vector <int> adj[300005];

bool cmp(int a, int b){
	return A[a] < A[b];
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> A[i];
	while(m--){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)vis[j] = 0;
		vis[i] = 1;
		int cur = A[i];
		set <pi> ms;
		for(auto j : adj[i])ms.insert({A[j], j});
		while(!ms.empty()){
			pi x = *ms.begin();
			while(!ms.empty() && vis[x.se])ms.erase(ms.begin()), x = *ms.begin();
			if(vis[x.se])break;
			ms.erase(ms.begin());
			if(x.fi > cur)break;
			cur += x.fi;
			vis[x.se] = 1;
			for(auto j : adj[x.se]){
				if(vis[j])continue;
				ms.insert({A[j], j});
			}
		}
		ans[i] = 1;
		for(int j=1;j<=n;j++)if(!vis[j])ans[i] = 0;
	}
	for(int i=1;i<=n;i++)cout << ans[i];
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 243 ms 7524 KB Output is correct
5 Correct 212 ms 7516 KB Output is correct
6 Correct 354 ms 7508 KB Output is correct
7 Correct 226 ms 7508 KB Output is correct
8 Correct 195 ms 7508 KB Output is correct
9 Correct 303 ms 7556 KB Output is correct
10 Correct 106 ms 7508 KB Output is correct
11 Correct 101 ms 7508 KB Output is correct
12 Correct 128 ms 7520 KB Output is correct
13 Correct 188 ms 7468 KB Output is correct
14 Correct 126 ms 7508 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Execution timed out 1083 ms 22700 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Execution timed out 1060 ms 19644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Execution timed out 1067 ms 21164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 243 ms 7524 KB Output is correct
5 Correct 212 ms 7516 KB Output is correct
6 Correct 354 ms 7508 KB Output is correct
7 Correct 226 ms 7508 KB Output is correct
8 Correct 195 ms 7508 KB Output is correct
9 Correct 303 ms 7556 KB Output is correct
10 Correct 106 ms 7508 KB Output is correct
11 Correct 101 ms 7508 KB Output is correct
12 Correct 128 ms 7520 KB Output is correct
13 Correct 188 ms 7468 KB Output is correct
14 Correct 126 ms 7508 KB Output is correct
15 Correct 5 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Execution timed out 1083 ms 22700 KB Time limit exceeded
18 Halted 0 ms 0 KB -