oj.uz

Submission #593624

# Submission time Handle Problem Language Result Execution time Memory
593624 2022-07-11T12:56:45 Z Blagojce Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 443620 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
 
const int mxn = 2e5 + 5;
 
int n, m;
vector<int> g[mxn];
ll a[mxn];
 
vector<int> S[mxn];
vector<int> G[mxn];
 
 
 
ll sum[mxn];
 
int v_count = 0;
int vis_ver[mxn];
int vis_edg[mxn];
 
vector<int> merge(int u, int v){
	vector<int> cand;
	for(auto vp : S[v]){
		if(vis_ver[vp] == v_count) continue;
		
		S[u].pb(vp);
		sum[u] += a[vp];
		vis_ver[vp] = v_count;
	}
	for(auto ep : G[v]){
		if(vis_edg[ep] == v_count || vis_ver[ep] == v_count) continue;
		G[u].pb(ep);
		cand.pb(ep);
		vis_edg[ep] = v_count;
	}
	return cand;
}
 
void expand(int u){
	++v_count;
	for(auto e : S[u]) vis_ver[e] = v_count;
	for(auto e : G[u]) vis_edg[e] = v_count;
	
	pq <pair<int,int> > Q;
	for(auto e : G[u]) Q.push({-a[e], e});
	
	while(!Q.empty()){
		int c = Q.top().nd;
		Q.pop();
		if(vis_ver[c] == v_count) continue;
		if(sum[u] < a[c]) continue;
		vector<int> cand = merge(u, c);
		for(auto c : cand){
			Q.push({-a[c], c});
		}
	}
	sort(all(G[u]));
	G[u].erase(unique(all(G[u])),G[u].end()); 
}
 
int main(){
	cin >> n >> m;
	fr(i, 0, n){
		cin >> a[i];
	}
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].pb(v);
		g[v].pb(u);
	}
	fr(i, 0, n){
		G[i] = g[i];
		S[i] = {i};
		sum[i] = a[i];
	}
	fr(i, 0, n){
		expand(i);
	}
	fr(i, 0, n){
		if((int)S[i].size() == n) cout<<1;
		else cout<<0;
	}
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 32 ms 22740 KB Output is correct
5 Correct 31 ms 23184 KB Output is correct
6 Correct 177 ms 30892 KB Output is correct
7 Correct 29 ms 22536 KB Output is correct
8 Correct 23 ms 21204 KB Output is correct
9 Correct 282 ms 40668 KB Output is correct
10 Correct 31 ms 23628 KB Output is correct
11 Correct 30 ms 23228 KB Output is correct
12 Correct 31 ms 21864 KB Output is correct
13 Correct 231 ms 40900 KB Output is correct
14 Correct 29 ms 22164 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Execution timed out 1008 ms 87160 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 1074 ms 443620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 1058 ms 190140 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 32 ms 22740 KB Output is correct
5 Correct 31 ms 23184 KB Output is correct
6 Correct 177 ms 30892 KB Output is correct
7 Correct 29 ms 22536 KB Output is correct
8 Correct 23 ms 21204 KB Output is correct
9 Correct 282 ms 40668 KB Output is correct
10 Correct 31 ms 23628 KB Output is correct
11 Correct 30 ms 23228 KB Output is correct
12 Correct 31 ms 21864 KB Output is correct
13 Correct 231 ms 40900 KB Output is correct
14 Correct 29 ms 22164 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14416 KB Output is correct
17 Execution timed out 1008 ms 87160 KB Time limit exceeded
18 Halted 0 ms 0 KB -