oj.uz

답안 #913848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
913848 2024-01-20T11:02:15 Z pragmatist Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 38268 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];
}
 
vector<int> g[N];

int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);         
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 23 ms 16532 KB Output is correct
5 Correct 23 ms 15596 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 18 ms 16472 KB Output is correct
8 Correct 16 ms 16220 KB Output is correct
9 Correct 6 ms 15196 KB Output is correct
10 Correct 25 ms 15596 KB Output is correct
11 Correct 27 ms 15268 KB Output is correct
12 Correct 16 ms 15192 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 6 ms 15752 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Execution timed out 1054 ms 34480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Execution timed out 1050 ms 33728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 251 ms 36608 KB Output is correct
3 Correct 217 ms 36512 KB Output is correct
4 Correct 215 ms 36988 KB Output is correct
5 Correct 138 ms 34236 KB Output is correct
6 Correct 86 ms 27552 KB Output is correct
7 Correct 126 ms 38268 KB Output is correct
8 Correct 113 ms 33208 KB Output is correct
9 Correct 90 ms 27328 KB Output is correct
10 Correct 138 ms 28092 KB Output is correct
11 Correct 230 ms 37080 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 23 ms 16532 KB Output is correct
5 Correct 23 ms 15596 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 18 ms 16472 KB Output is correct
8 Correct 16 ms 16220 KB Output is correct
9 Correct 6 ms 15196 KB Output is correct
10 Correct 25 ms 15596 KB Output is correct
11 Correct 27 ms 15268 KB Output is correct
12 Correct 16 ms 15192 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 6 ms 15752 KB Output is correct
15 Correct 4 ms 14940 KB Output is correct
16 Correct 4 ms 14940 KB Output is correct
17 Execution timed out 1054 ms 34480 KB Time limit exceeded
18 Halted 0 ms 0 KB -