oj.uz

Submission #913930

# Submission time Handle Problem Language Result Execution time Memory
913930 2024-01-20T14:22:53 Z pragmatist Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 37820 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 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]);
    				}
    			}
    		}  
    		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;
    				}
    			}			
    		}
    		  
    		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 4 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14996 KB Output is correct
4 Correct 25 ms 16476 KB Output is correct
5 Correct 23 ms 15700 KB Output is correct
6 Correct 6 ms 15192 KB Output is correct
7 Correct 17 ms 16476 KB Output is correct
8 Correct 16 ms 16220 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 21 ms 15180 KB Output is correct
11 Correct 26 ms 15188 KB Output is correct
12 Correct 16 ms 15196 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct
14 Correct 6 ms 15708 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 226 ms 32452 KB Output is correct
3 Correct 219 ms 36348 KB Output is correct
4 Correct 214 ms 36544 KB Output is correct
5 Correct 111 ms 33476 KB Output is correct
6 Correct 86 ms 26668 KB Output is correct
7 Correct 119 ms 37820 KB Output is correct
8 Correct 92 ms 32868 KB Output is correct
9 Correct 103 ms 26608 KB Output is correct
10 Correct 123 ms 27964 KB Output is correct
11 Correct 168 ms 36800 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14996 KB Output is correct
4 Correct 25 ms 16476 KB Output is correct
5 Correct 23 ms 15700 KB Output is correct
6 Correct 6 ms 15192 KB Output is correct
7 Correct 17 ms 16476 KB Output is correct
8 Correct 16 ms 16220 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 21 ms 15180 KB Output is correct
11 Correct 26 ms 15188 KB Output is correct
12 Correct 16 ms 15196 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct
14 Correct 6 ms 15708 KB Output is correct
15 Correct 4 ms 14940 KB Output is correct
16 Correct 3 ms 14768 KB Output is correct
17 Execution timed out 1074 ms 29888 KB Time limit exceeded
18 Halted 0 ms 0 KB -