oj.uz

Submission #593627

# Submission time Handle Problem Language Result Execution time Memory
593627 2022-07-11T12:59:35 Z Blagojce Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 417412 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});
		}
	}
	for(int i = (int)G[u].size()-1; i >= 0; i --){
		if(vis_ver[G[u][i]] == v_count){
			swap(G[u][i], G[u].back());
			G[u].pop_back();
		}
	}
}
 
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 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 30 ms 22732 KB Output is correct
5 Correct 33 ms 23120 KB Output is correct
6 Correct 154 ms 30856 KB Output is correct
7 Correct 30 ms 22476 KB Output is correct
8 Correct 22 ms 21192 KB Output is correct
9 Correct 296 ms 40584 KB Output is correct
10 Correct 29 ms 23628 KB Output is correct
11 Correct 29 ms 23212 KB Output is correct
12 Correct 28 ms 21836 KB Output is correct
13 Correct 177 ms 41004 KB Output is correct
14 Correct 33 ms 22148 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14304 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Execution timed out 1045 ms 100448 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Execution timed out 1069 ms 417412 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 1096 ms 186892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 30 ms 22732 KB Output is correct
5 Correct 33 ms 23120 KB Output is correct
6 Correct 154 ms 30856 KB Output is correct
7 Correct 30 ms 22476 KB Output is correct
8 Correct 22 ms 21192 KB Output is correct
9 Correct 296 ms 40584 KB Output is correct
10 Correct 29 ms 23628 KB Output is correct
11 Correct 29 ms 23212 KB Output is correct
12 Correct 28 ms 21836 KB Output is correct
13 Correct 177 ms 41004 KB Output is correct
14 Correct 33 ms 22148 KB Output is correct
15 Correct 8 ms 14304 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Execution timed out 1045 ms 100448 KB Time limit exceeded
18 Halted 0 ms 0 KB -