Submission #970509

#	Time	Username	Problem	Language	Result	Execution time	Memory
970509		yellowtoad	Stranded Far From Home (BOI22_island)	C++17	10 / 100	412 ms	58864 KiB

island

#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;

long long n, m, p[200010], sum[200010], vis[200010], scc[200010], cnt, in[200010];
pair<long long,int> a[200010];
vector<int> edge[200010], ed[200010], rev[200010], post;

int dsu(int u) {
	if (u == p[u]) return u;
	return p[u] = dsu(p[u]);
}

void dfs(int u) {
	vis[u] = 1;
	for (int i = 0; i < ed[u].size(); i++) if (!vis[ed[u][i]]) dfs(ed[u][i]);
	post.push_back(u);
}

void rdfs(int u) {
	scc[u] = cnt;
	for (int i = 0; i < rev[u].size(); i++) if (!scc[rev[u][i]]) rdfs(rev[u][i]);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].f;
		a[i].s = p[i] = i;
		sum[i] = a[i].f;
	}
	sort(a+1,a+n+1);
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		int u = a[i].s;
		vis[u] = 1;
		for (int j = 0; j < edge[u].size(); j++) {
			if (!vis[edge[u][j]]) continue;
			ed[u].push_back(edge[u][j]);
			rev[edge[u][j]].push_back(u);
			if (dsu(u) != dsu(edge[u][j])) {
				if (sum[dsu(edge[u][j])] >= a[i].f) ed[edge[u][j]].push_back(u), rev[u].push_back(edge[u][j]);;
				sum[dsu(u)] += sum[dsu(edge[u][j])];
				p[dsu(edge[u][j])] = p[dsu(u)];
			}
		}
	}
	for (int i = 1; i <= n; i++) vis[i] = 0;
	for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);
	for (int i = post.size()-1; i >= 0; i--) {
		if (!scc[post[i]]) {
			++cnt;
			rdfs(post[i]);
		}
	}
	for (int i = 1; i <= n; i++) for (int j = 0; j < ed[i].size(); j++) if (scc[i] != scc[ed[i][j]]) in[scc[ed[i][j]]]++;
	for (int i = 1; i <= n; i++) cout << (in[scc[i]] == 0);
	cout << endl;
}

Compilation message (stderr)

island.cpp: In function 'void dfs(int)':
island.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (int i = 0; i < ed[u].size(); i++) if (!vis[ed[u][i]]) dfs(ed[u][i]);
      |                  ~~^~~~~~~~~~~~~~
island.cpp: In function 'void rdfs(int)':
island.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < rev[u].size(); i++) if (!scc[rev[u][i]]) rdfs(rev[u][i]);
      |                  ~~^~~~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int j = 0; j < edge[u].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~
island.cpp:64:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 1; i <= n; i++) for (int j = 0; j < ed[i].size(); j++) if (scc[i] != scc[ed[i][j]]) in[scc[ed[i][j]]]++;
      |                                               ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35