oj.uz

Submission #702211

# Submission time Handle Problem Language Result Execution time Memory
702211 2023-02-23T10:22:25 Z lovrot Stranded Far From Home (BOI22_island) C++17
25 / 100
 195 ms 24700 KB 
#include <vector>
#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define pb push_back

using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 

const int N = 2e5 + 10; 

int n, m, to[N], U[N], sol[N];
ll S[N], SUM[N];

vector<int> g[N]; 
vector<pair<ll, int>> p; 

int Find(int u) {
	if(u == U[u]) return u; 
	return U[u] = Find(U[u]); 
}

void Union(int u, int v) {
	v = Find(v); 
	U[v] = u; 
	SUM[u] += SUM[v]; 
	if(!to[v] || S[to[v]] == S[v]) to[v] = u; 
}

int main() {
	for(int i = 0; i < N; i++) U[i] = i;

	scanf("%d%d", &n, &m); 

	for(int i = 1; i <= n; i++) {
		scanf("%lld", S + i); 
		p.pb({S[i], i}); 
	}

	sort(p.begin(), p.end()); 

	for(int i = 0; i < m; i++) {
		int u, v; 
		scanf("%d%d", &u, &v); 
		if(S[u] < S[v] || S[u] == S[v] && u < v) swap(u, v);
		g[u].pb(v); 
	}

	for(pair<ll, int> u : p) {
		SUM[u.Y] = S[u.Y]; 
		for(int v : g[u.Y]) Union(u.Y, v); 
	}

	reverse(p.begin(), p.end()); 
	to[p[0].Y] = 0; 
	SUM[0] = 0; 
	sol[0] = 1;

	for(pair<ll, int> u : p)
		if(sol[to[u.Y]] && SUM[u.Y] >= S[to[u.Y]]) sol[u.Y] = true; 

	for(int i = 1; i <= n; i++) printf("%d", sol[i]); 
	printf("\n");
	return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:50:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |   if(S[u] < S[v] || S[u] == S[v] && u < v) swap(u, v);
      |                     ~~~~~~~~~~~~~^~~~~~~~
island.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%lld", S + i);
      |   ~~~~~^~~~~~~~~~~~~~~
island.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 5 ms 5716 KB Output is correct
3 Correct 4 ms 5776 KB Output is correct
4 Incorrect 5 ms 5924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5788 KB Output is correct
2 Correct 4 ms 5784 KB Output is correct
3 Correct 134 ms 22500 KB Output is correct
4 Correct 158 ms 23492 KB Output is correct
5 Correct 145 ms 21488 KB Output is correct
6 Correct 133 ms 21924 KB Output is correct
7 Correct 135 ms 21924 KB Output is correct
8 Correct 144 ms 24376 KB Output is correct
9 Correct 153 ms 20820 KB Output is correct
10 Correct 112 ms 18288 KB Output is correct
11 Correct 153 ms 23416 KB Output is correct
12 Correct 144 ms 21684 KB Output is correct
13 Correct 144 ms 24668 KB Output is correct
14 Correct 155 ms 24700 KB Output is correct
15 Correct 128 ms 24388 KB Output is correct
16 Correct 93 ms 23600 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5788 KB Output is correct
2 Correct 179 ms 22228 KB Output is correct
3 Correct 195 ms 22336 KB Output is correct
4 Correct 165 ms 24456 KB Output is correct
5 Correct 139 ms 22984 KB Output is correct
6 Correct 172 ms 22372 KB Output is correct
7 Correct 154 ms 24452 KB Output is correct
8 Correct 162 ms 24464 KB Output is correct
9 Correct 97 ms 23620 KB Output is correct
10 Correct 127 ms 21916 KB Output is correct
11 Correct 146 ms 20680 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5816 KB Output is correct
2 Incorrect 173 ms 21572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 5 ms 5716 KB Output is correct
3 Correct 4 ms 5776 KB Output is correct
4 Incorrect 5 ms 5924 KB Output isn't correct
5 Halted 0 ms 0 KB -