Submission #578150

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
578150	2022-06-16T05:59:35 Z	8e7	Stranded Far From Home (BOI22_island)	C++17	25 / 100	1000 ms	102208 KB

island

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...); }
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxc 31
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<30;
vector<int> adj[maxn];
ll sum[maxc][maxn];
int mi[maxc][maxn], comp[maxc][maxn], smi[maxc][maxn];
int idx[maxc][maxn];
ll w[maxn];
int lev[maxn];
 
bool vis[maxn], tv[maxn];
void dfs(int n, int id, int l) {
	vis[n] = 1;	
	sum[l][id] += w[n];
	comp[l][n] = id;
	for (int v:adj[n]) {
		if (!vis[v] && lev[v] < l) dfs(v, id, l);
	}
}
int main() {
	io
	int n, m;
	cin >> n >> m;
	ll tot = 0;
	for (int i = 1;i <= n;i++) cin >> w[i], tot += w[i];
	for (int i = 0;i < m;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) {
		ll tmp = w[i];
		while (tmp >= 2) {
			lev[i]++;
			tmp >>= 1;
		}
	}
	for (int j = 0;j <= n;j++) mi[0][j] = smi[0][j] = inf;
	for (int i = 1;i < maxc;i++) {
		for (int j = 1;j <= n;j++) vis[j] = 0, mi[i][j] = smi[i][j] = inf;
		mi[i][0] = smi[i][0] = inf;
		int cnt = 1;
		for (int j = 1;j <= n;j++) {
			if (!vis[j] && lev[j] < i) {
				dfs(j, cnt, i);
				//debug(i, j, cnt, sum[i][c]);
				cnt++;
			}
		}
		for (int j = 1;j <= n;j++) {
			if (lev[j] >= i) {
				for (int k:adj[j]) {
					if (lev[k] < i) {
						int c = comp[i][k];
						if (w[j] < mi[i][c]) {
							smi[i][c] = mi[i][c];
							mi[i][c] = w[j];
							idx[i][c] = j;
						} else {
							smi[i][c] = min(smi[i][c], (int)w[j]);
						}
					}
				}
			}
		}
	}
	string ans;
	for (int i = 1;i <= n;i++) {
		int cur = lev[i];
		bool poss = 0, fi = 1;
		while (cur < maxc) {
			ll p = 0;
			int val = inf;
			if (fi) {
				fi = 0;
				p = w[i];
				vector<int> v;
				for (int j:adj[i]) {
					if (lev[j] < cur && !tv[comp[cur][j]]) {
						int c = comp[cur][j];
						tv[c] = 1;
						p += sum[cur][c];
						v.push_back(c);
						if (idx[cur][c] == i) val = min(val, smi[cur][c]);
						else val = min(val, mi[cur][c]);
					} else if (lev[j] >= cur) {
						val = min(val, (int)w[j]);
					}
				}
				for (int j:v) tv[j] = 0;
			} else {
				val = min(val, mi[cur][comp[cur][i]]);
			}
			if (comp[cur][i]) p += sum[cur][comp[cur][i]];
			debug(cur, p, val);
			if (p == tot) {
				poss = 1;
				break;
			} else if (p < val) {
				break;
			} else {
				cur++;
			}
		}
		debug();
		if (poss) ans += '1';
		else ans += '0';
	}
	cout << ans << "\n";
}
/*
5 4
7 10 1 5 9 
1 2 
3 5 
3 4 
4 1 
*/

Compilation message

island.cpp: In function 'int main()':
island.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
island.cpp:115:4: note: in expansion of macro 'debug'
  115 |    debug(cur, p, val);
      |    ^~~~~
island.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
island.cpp:125:3: note: in expansion of macro 'debug'
  125 |   debug();
      |   ^~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5716 KB	Output is correct
2	Correct	3 ms	5716 KB	Output is correct
3	Correct	3 ms	5716 KB	Output is correct
4	Correct	7 ms	6228 KB	Output is correct
5	Correct	5 ms	6228 KB	Output is correct
6	Correct	5 ms	5844 KB	Output is correct
7	Correct	5 ms	6100 KB	Output is correct
8	Correct	4 ms	5972 KB	Output is correct
9	Correct	5 ms	6612 KB	Output is correct
10	Correct	5 ms	6356 KB	Output is correct
11	Correct	4 ms	6356 KB	Output is correct
12	Correct	5 ms	6100 KB	Output is correct
13	Correct	5 ms	6740 KB	Output is correct
14	Correct	5 ms	6684 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5716 KB	Output is correct
2	Correct	3 ms	5716 KB	Output is correct
3	Correct	288 ms	70120 KB	Output is correct
4	Correct	538 ms	88764 KB	Output is correct
5	Correct	318 ms	65580 KB	Output is correct
6	Correct	334 ms	67240 KB	Output is correct
7	Correct	320 ms	67264 KB	Output is correct
8	Correct	293 ms	64512 KB	Output is correct
9	Correct	285 ms	67452 KB	Output is correct
10	Correct	275 ms	69188 KB	Output is correct
11	Correct	227 ms	67784 KB	Output is correct
12	Execution timed out	1044 ms	90204 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5716 KB	Output is correct
2	Correct	315 ms	86672 KB	Output is correct
3	Correct	305 ms	87160 KB	Output is correct
4	Correct	252 ms	76208 KB	Output is correct
5	Correct	664 ms	98392 KB	Output is correct
6	Correct	298 ms	86896 KB	Output is correct
7	Correct	285 ms	76228 KB	Output is correct
8	Correct	238 ms	76168 KB	Output is correct
9	Correct	183 ms	86412 KB	Output is correct
10	Correct	462 ms	89380 KB	Output is correct
11	Correct	708 ms	102208 KB	Output is correct

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5716 KB	Output is correct
2	Correct	403 ms	70620 KB	Output is correct
3	Correct	363 ms	73708 KB	Output is correct
4	Correct	342 ms	67048 KB	Output is correct
5	Correct	311 ms	64740 KB	Output is correct
6	Correct	334 ms	63164 KB	Output is correct
7	Correct	200 ms	64520 KB	Output is correct
8	Correct	203 ms	86428 KB	Output is correct
9	Correct	442 ms	48004 KB	Output is correct
10	Execution timed out	1069 ms	85616 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5716 KB	Output is correct
2	Correct	3 ms	5716 KB	Output is correct
3	Correct	3 ms	5716 KB	Output is correct
4	Correct	7 ms	6228 KB	Output is correct
5	Correct	5 ms	6228 KB	Output is correct
6	Correct	5 ms	5844 KB	Output is correct
7	Correct	5 ms	6100 KB	Output is correct
8	Correct	4 ms	5972 KB	Output is correct
9	Correct	5 ms	6612 KB	Output is correct
10	Correct	5 ms	6356 KB	Output is correct
11	Correct	4 ms	6356 KB	Output is correct
12	Correct	5 ms	6100 KB	Output is correct
13	Correct	5 ms	6740 KB	Output is correct
14	Correct	5 ms	6684 KB	Output is correct
15	Correct	3 ms	5716 KB	Output is correct
16	Correct	3 ms	5716 KB	Output is correct
17	Correct	288 ms	70120 KB	Output is correct
18	Correct	538 ms	88764 KB	Output is correct
19	Correct	318 ms	65580 KB	Output is correct
20	Correct	334 ms	67240 KB	Output is correct
21	Correct	320 ms	67264 KB	Output is correct
22	Correct	293 ms	64512 KB	Output is correct
23	Correct	285 ms	67452 KB	Output is correct
24	Correct	275 ms	69188 KB	Output is correct
25	Correct	227 ms	67784 KB	Output is correct
26	Execution timed out	1044 ms	90204 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-