oj.uz

Submission #912375

# Submission time Handle Problem Language Result Execution time Memory
912375 2024-01-19T10:43:48 Z pragmatist Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 26632 KB 
/*
JUDGE_ID : 331438IX
*/
 
#include<iostream>
#include<cassert>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<map>
 
using namespace std;
 
const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int MOD = (int)998244353;
const long long INF = (long long)1e18 + 7; 
 
int mult(int x, int y) {
	return 1ll*x*y%MOD;
}
 
int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}
 
int sub(int x, int y) {
	x -= y;
	if(x < 0) {
		x += MOD;
	}
	return x;
}
 
bool is_prime(int x) {
	if(x == 1) {
		return 0;
	}
	for(int i = 2; i * i <= x; ++i) {
		if(x % i == 0) {
			return 0;
		}
	}
	return 1;
}
 
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];
}
 
int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(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;
		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(auto [u, v] : e) {
			if(a[u] <= a[b[i]] && a[v] <= a[b[i]]) {
				comb(u, v);
			}
		}
		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(auto [u, v] : e) {
			if(a[u] <= a[b[i]]) {
				long long cur = s[get(u)];
				if(cur >= a[v]) {
					comb(u, v);
				}
			}
			if(a[v] <= a[b[i]]) {
				long long cur = s[get(v)];
				if(cur >= a[u]) {
					comb(u, v);
				}
			}
		}
		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 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 68 ms 8740 KB Output is correct
5 Correct 72 ms 7756 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 50 ms 8120 KB Output is correct
8 Correct 45 ms 8276 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 68 ms 7268 KB Output is correct
11 Correct 73 ms 7028 KB Output is correct
12 Correct 41 ms 7260 KB Output is correct
13 Correct 2 ms 6860 KB Output is correct
14 Correct 7 ms 7236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Execution timed out 1091 ms 18904 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 6744 KB Output is correct
2 Execution timed out 1057 ms 18444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 214 ms 22780 KB Output is correct
3 Correct 241 ms 26256 KB Output is correct
4 Correct 200 ms 26632 KB Output is correct
5 Correct 69 ms 23236 KB Output is correct
6 Correct 57 ms 16836 KB Output is correct
7 Correct 79 ms 25672 KB Output is correct
8 Correct 68 ms 21700 KB Output is correct
9 Correct 112 ms 18560 KB Output is correct
10 Correct 63 ms 17088 KB Output is correct
11 Correct 157 ms 26604 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 68 ms 8740 KB Output is correct
5 Correct 72 ms 7756 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 50 ms 8120 KB Output is correct
8 Correct 45 ms 8276 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 68 ms 7268 KB Output is correct
11 Correct 73 ms 7028 KB Output is correct
12 Correct 41 ms 7260 KB Output is correct
13 Correct 2 ms 6860 KB Output is correct
14 Correct 7 ms 7236 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Execution timed out 1091 ms 18904 KB Time limit exceeded
18 Halted 0 ms 0 KB -