oj.uz

Submission #722928

# Submission time Handle Problem Language Result Execution time Memory
722928 2023-04-13T05:52:54 Z MurotY Stranded Far From Home (BOI22_island) C++14
0 / 100
 333 ms 36104 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz size()
using namespace std;
const double pi = 2 * acos(0.0);
const ll N=1e6+7, M=998244353;
vector <pair <ll,ll>> g[N];
ll a[N];
 
void solve()
{
	int n, m;
	cin >> n >> m;
	
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=m;i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back({a[y], y});
		g[y].push_back({a[x], x});
	}
	for (int i=1;i<=n;i++) sort(all(g[i]));
    if (n <= 2000 && m <= 2000){
		for (int i=1;i<=n;i++){
			priority_queue <ll, vector <ll>, greater <ll>> q;
			vector <bool> u(n+5, 0);
			q.push(i);
			ll sum=a[i], cnt=0;
			while (!q.empty()){
			     ll x=q.top();
			     q.pop();
			     if (u[x]) continue;
				u[x]=1; cnt++;
				for (auto l:g[x]){
					if (sum >= l.ff) {
						sum+=l.ff;
						q.push(l.ss);
					}
				}
			}
			if (cnt == n) cout << "1";
			else cout << "0";
		}		
	}
	return ;
}
int main(){
//	ios;
	int t=1;	
//	cin >> t;
	while (t--){ 
	    solve();
	    cout << "\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23764 KB Output is correct
2 Correct 14 ms 23676 KB Output is correct
3 Correct 16 ms 23764 KB Output is correct
4 Incorrect 333 ms 23904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Incorrect 286 ms 36104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23888 KB Output is correct
2 Incorrect 266 ms 35700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 300 ms 35940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23764 KB Output is correct
2 Correct 14 ms 23676 KB Output is correct
3 Correct 16 ms 23764 KB Output is correct
4 Incorrect 333 ms 23904 KB Output isn't correct
5 Halted 0 ms 0 KB -