oj.uz

Submission #912276

# Submission time Handle Problem Language Result Execution time Memory
912276 2024-01-19T09:23:16 Z pragmatist Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 21976 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[v] && a[u] == 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[v]) {
    				comb(u, v);
    			}
    		}
    	}
    	i = r;
    }
    for(int i = 1; i <= n; ++i) {
    	cout << ans[i];
    }
    return 0;
 }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6840 KB Output is correct
4 Incorrect 25 ms 8488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 Execution timed out 1069 ms 19060 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 6748 KB Output is correct
2 Execution timed out 1029 ms 18380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Incorrect 165 ms 21976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6840 KB Output is correct
4 Incorrect 25 ms 8488 KB Output isn't correct
5 Halted 0 ms 0 KB -