oj.uz

Submission #703504

# Submission time Handle Problem Language Result Execution time Memory
703504 2023-02-27T14:28:05 Z Chal1shkan Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 14024 KB 
# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 2e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 998244353;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;

ll n, m, s[maxn];
vector <ll> g[maxn];
bool used[maxn];

void bfs (ll st)
{
	priority_queue <pair <int, int> > q;
	queue <int> w;
	ll sum = s[st];
	w.push(st);
	while (!w.empty())
	{
 		ll v = w.front();
		w.pop();
		if (used[v]) continue;
		used[v] = 1;
		for (ll to : g[v])
		{
			if (!used[to])
			{
				q.push({-s[to], to});
			}
		}
		while (!q.empty())
		{
			if (sum >= -q.top().ff)
			{
				sum += -q.top().ff;
				w.push(q.top().ss);
				q.pop();
			}
			else
			{
				break;
			}
		}
	}
}

void ma1n (/* SABR */)
{
	cin >> n >> m;
	for (ll i = 1; i <= n; ++i)
	{
		cin >> s[i];
	}
	for (ll i = 1, u, v; i <= m; ++i)
	{
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);	
	}	
	string ans = "";
	for (ll i = 1; i <= n; ++i)
	{
		bfs(i);
		bool ok = 1;
		for (ll j = 1; j <= n; ++j)
		{
			if (!used[j]) ok = 0;
		}
		ans += char(ok + '0');
		memset(used, 0, sizeof(used));
	}
	cout << ans;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;	
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 2 ms 5204 KB Output is correct
4 Correct 84 ms 5304 KB Output is correct
5 Correct 79 ms 5204 KB Output is correct
6 Correct 130 ms 5292 KB Output is correct
7 Correct 89 ms 5328 KB Output is correct
8 Correct 73 ms 5284 KB Output is correct
9 Correct 136 ms 5332 KB Output is correct
10 Correct 67 ms 5340 KB Output is correct
11 Correct 72 ms 5336 KB Output is correct
12 Correct 60 ms 5332 KB Output is correct
13 Correct 110 ms 5324 KB Output is correct
14 Correct 72 ms 5332 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Execution timed out 1084 ms 12932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Execution timed out 1079 ms 13932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 2 ms 5204 KB Output is correct
4 Correct 84 ms 5304 KB Output is correct
5 Correct 79 ms 5204 KB Output is correct
6 Correct 130 ms 5292 KB Output is correct
7 Correct 89 ms 5328 KB Output is correct
8 Correct 73 ms 5284 KB Output is correct
9 Correct 136 ms 5332 KB Output is correct
10 Correct 67 ms 5340 KB Output is correct
11 Correct 72 ms 5336 KB Output is correct
12 Correct 60 ms 5332 KB Output is correct
13 Correct 110 ms 5324 KB Output is correct
14 Correct 72 ms 5332 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 2 ms 5204 KB Output is correct
17 Execution timed out 1073 ms 14024 KB Time limit exceeded
18 Halted 0 ms 0 KB -