oj.uz

Submission #593613

# Submission time Handle Problem Language Result Execution time Memory
593613 2022-07-11T12:34:41 Z Blagojce Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 387100 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];


bool yes[mxn];


vector<int> merge(int u, int v){
	vector<int> cand;
	for(auto vp : S[v]){
		if(vis_ver[vp] == v_count) continue;
		yes[u] |= yes[vp];
		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() && !yes[u]){
		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});
		}
	}
}

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];
	}
	
	vector<int> V;
	fr(i, 0, n) V.pb(i);
	sort(all(V), [](const int &i, const int &j){
		return a[i] > a[j];
	});
	
	yes[V[0]] = true;
	fr(i, 1, n){
		expand(V[i]);
	}
	fr(i, 0, n){
		if(yes[i]) cout<<1;
		else cout<<0;
	}
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 7 ms 14340 KB Output is correct
4 Correct 133 ms 26536 KB Output is correct
5 Correct 50 ms 24052 KB Output is correct
6 Correct 30 ms 18232 KB Output is correct
7 Correct 125 ms 26144 KB Output is correct
8 Correct 99 ms 24668 KB Output is correct
9 Correct 333 ms 40708 KB Output is correct
10 Correct 23 ms 21980 KB Output is correct
11 Correct 27 ms 22356 KB Output is correct
12 Correct 20 ms 18228 KB Output is correct
13 Correct 45 ms 30704 KB Output is correct
14 Correct 51 ms 22656 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Correct 7 ms 14340 KB Output is correct
4 Correct 133 ms 26536 KB Output is correct
5 Correct 50 ms 24052 KB Output is correct
6 Correct 30 ms 18232 KB Output is correct
7 Correct 125 ms 26144 KB Output is correct
8 Correct 99 ms 24668 KB Output is correct
9 Correct 333 ms 40708 KB Output is correct
10 Correct 23 ms 21980 KB Output is correct
11 Correct 27 ms 22356 KB Output is correct
12 Correct 20 ms 18228 KB Output is correct
13 Correct 45 ms 30704 KB Output is correct
14 Correct 51 ms 22656 KB Output is correct
15 Correct 9 ms 14420 KB Output is correct
16 Correct 8 ms 14292 KB Output is correct
17 Execution timed out 1069 ms 92332 KB Time limit exceeded
18 Halted 0 ms 0 KB -