oj.uz

Submission #913932

# Submission time Handle Problem Language Result Execution time Memory
913932 2024-01-20T14:40:59 Z pragmatist Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 55036 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];
vector<int> pos[N];
vector<int> need[N];
bool ans[N];
 
set<pair<long long, int> > have;
long long s[N];

void comb(int u, int v) {
	int l = p[u];
	int r = p[v];
	if(l == r) {
		return;
	}
	have.erase({s[l], l});
	have.erase({s[r], r});
	if((int)pos[l].size() > (int)pos[r].size()) {
		for(auto x : pos[r]) {
			p[x] = l;
			pos[l].push_back(x);
		}	
	    for(auto x : need[r]) {
	    	need[l].push_back(x);
	    }
		pos[r].clear();
		need[r].clear();        		
		s[l] += s[r];
		if(!need[l].empty()) {
			have.insert({s[l], l});
		}
	} else {
		for(auto x : pos[l]) {
			p[x] = r;
			pos[r].push_back(x);
		}	
		for(auto x : need[l]) {
			need[r].push_back(x);
		}
		pos[l].clear();
		need[l].clear();
		s[r] += s[l];
		if(!need[r].empty()) {
			have.insert({s[r], r});
		}
	}
}
 
long long val[N];
 
int b[N]; 
 
bool cmp2(int i, int j) {
	return a[i] < a[j];
}
 
vector<int> g[N];

int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[i] = i;
		b[i] = i;
		s[i] = a[i];
		pos[i].push_back(i);
		need[i].push_back(i);
	}
	for(int i = 1; i <= n; ++i) {
		ans[i] = 1;
	}    
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}    
	sort(b+1, b+1+n, cmp2);
	for(int i = 1; i <= n; ++i) {
		if(a[b[i]] == a[b[n]]) {
			break;
		}
		int r = i;
		while(r<n && a[b[r]] == a[b[r+1]]) {
			r++;
		}
		for(int k = i; k <= r; ++k) {
			have.insert({a[b[r]], b[k]});
		}
		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 k = i; k <= r; ++k) {
			for(auto u : g[b[k]]) {
				long long cur = s[p[b[k]]];
				if(cur >= a[u]) {
					comb(u, b[k]);
				}
			}
		}
		for(auto [cur, k] : have) {
			if(cur < a[b[r+1]]) {
				for(auto x : need[k]) {
					ans[x] = 0;
				}
				need[k].clear();
			} else {
				break;
			}
		}
		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 5 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 10 ms 19292 KB Output is correct
5 Correct 12 ms 19292 KB Output is correct
6 Correct 6 ms 19032 KB Output is correct
7 Correct 9 ms 19292 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 7 ms 19292 KB Output is correct
10 Correct 10 ms 19292 KB Output is correct
11 Correct 13 ms 19548 KB Output is correct
12 Correct 11 ms 19292 KB Output is correct
13 Correct 7 ms 19292 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19192 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Execution timed out 1061 ms 40072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Execution timed out 1057 ms 39744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19288 KB Output is correct
2 Correct 538 ms 46896 KB Output is correct
3 Correct 523 ms 45844 KB Output is correct
4 Correct 594 ms 46828 KB Output is correct
5 Correct 106 ms 38948 KB Output is correct
6 Correct 97 ms 38156 KB Output is correct
7 Correct 234 ms 52444 KB Output is correct
8 Correct 189 ms 51032 KB Output is correct
9 Correct 191 ms 34640 KB Output is correct
10 Correct 590 ms 55036 KB Output is correct
11 Correct 488 ms 52924 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 10 ms 19292 KB Output is correct
5 Correct 12 ms 19292 KB Output is correct
6 Correct 6 ms 19032 KB Output is correct
7 Correct 9 ms 19292 KB Output is correct
8 Correct 9 ms 19292 KB Output is correct
9 Correct 7 ms 19292 KB Output is correct
10 Correct 10 ms 19292 KB Output is correct
11 Correct 13 ms 19548 KB Output is correct
12 Correct 11 ms 19292 KB Output is correct
13 Correct 7 ms 19292 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 6 ms 19192 KB Output is correct
16 Correct 7 ms 19036 KB Output is correct
17 Execution timed out 1061 ms 40072 KB Time limit exceeded
18 Halted 0 ms 0 KB -