oj.uz

Submission #969400

# Submission time Handle Problem Language Result Execution time Memory
969400 2024-04-25T06:04:16 Z aeg Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 38248 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)2e5 + 7;

int n, m, a[N], p[N];
bool ans[N];
vector<int> pos[N];

int get(int v) {
	return (p[v] == v ? v : p[v] = get(p[v]));
}
long long s[N];

void comb(int u, int v) {
	u = get(u);
	v = get(v);
	if(u == v) {
		return;
	}
	p[u] = v;
	s[v] += s[u];
}

long long val[N];

int b[N]; 

bool cmp2(int i, int j) {
	return a[i] < a[j];
}

vector<int> g[N];

int main() {	
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	int mx = 0;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		mx = max(mx, a[i]);
		p[i] = i;
		b[i] = i;
		s[i] = a[i];
	}
	for(int i = 1; i <= n; ++i) {
		ans[i] = 1;
	}    
	vector<pair<int, int> > e;
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		e.push_back({u, v});
	}    
	sort(b+1, b+1+n, cmp2);
	for(int i = 1; i <= n; ++i) {
		if(a[b[i]] == mx) {
			break;
		}
		int r = i;
		while(r<n && a[b[r]] == a[b[r+1]]) {
			r++;
		}             
		for(int j = 1; j <= n; ++j) {
			pos[j].clear();
		}
		for(int k = i; k <= r; ++k) {
			for(auto u : g[b[k]]) {
				if(a[u] <= a[b[k]]) {
					comb(u, b[k]);
				}
			}
		}  
		for(int j = 1; j <= n; ++j) {
		pos[get(j)].push_back(j);
		}
		for(int j = 1; j <= n; ++j) {
			long long cur = s[j];
			if(cur < a[b[r+1]]) {
				for(auto x : pos[j]) {
					ans[x] = 0;
				}
			}			
		}
		for(int k = i; k <= r; ++k) {
			for(auto u : g[b[k]]) {
				long long cur = s[get(b[k])];
				if(cur >= a[u]) {
					comb(u, b[k]);
				}
			}
		}  
		i = r;
	}
	for(int i = 1; i <= n; ++i) {
		cout << ans[i];
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15192 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14996 KB Output is correct
4 Correct 26 ms 16476 KB Output is correct
5 Correct 23 ms 15960 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 17 ms 16476 KB Output is correct
8 Correct 15 ms 16220 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 22 ms 15196 KB Output is correct
11 Correct 26 ms 15184 KB Output is correct
12 Correct 20 ms 15340 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 6 ms 15520 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 198 ms 36548 KB Output is correct
3 Correct 204 ms 36668 KB Output is correct
4 Correct 197 ms 36892 KB Output is correct
5 Correct 98 ms 34144 KB Output is correct
6 Correct 91 ms 27488 KB Output is correct
7 Correct 104 ms 38248 KB Output is correct
8 Correct 88 ms 32708 KB Output is correct
9 Correct 90 ms 27512 KB Output is correct
10 Correct 109 ms 28124 KB Output is correct
11 Correct 143 ms 37036 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15192 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14996 KB Output is correct
4 Correct 26 ms 16476 KB Output is correct
5 Correct 23 ms 15960 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 17 ms 16476 KB Output is correct
8 Correct 15 ms 16220 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 22 ms 15196 KB Output is correct
11 Correct 26 ms 15184 KB Output is correct
12 Correct 20 ms 15340 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 6 ms 15520 KB Output is correct
15 Correct 3 ms 14936 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Execution timed out 1036 ms 34380 KB Time limit exceeded
18 Halted 0 ms 0 KB -