Submission #578210

#	Time	Username	Problem	Language	Result	Execution time	Memory
578210		asbsfds	Stranded Far From Home (BOI22_island)	C++14	0 / 100	571 ms	93576 KiB

island

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;

int n, m;
vector< int > graph[maxn];
int niz[maxn];
bool bio[maxn];
int parr[maxn], siz[maxn];
vector< int > s[maxn];
set< pair<int, int> > graph2[maxn];
int whs[maxn];
vector< pair<int, int> > v;

int fin(int x) {
	if (x == parr[x]) return x;
	return parr[x] = fin(parr[x]);
}

void merg(int a, int b) {
	a = fin(a);
	b = fin(b);
	if (a == b) return;
	
	graph2[a].erase({niz[b], b});
	graph2[b].erase({niz[a], a});
	
	if (graph2[a].size() < graph2[b].size()) swap(a, b);
	parr[b] = a;
	siz[a] += siz[b];
	for (auto iter : graph2[b]) {
		graph2[a].insert(iter);
	}
	
	int pa = whs[a], pb = whs[b];
	if (s[pa].size() < s[pb].size()) swap(pa, pb);
	whs[a] = pa;
	for (int ac : s[pb]) s[pa].push_back(ac);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", niz+i);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	for (int i = 1; i <= n; i++) {
		parr[i] = i, siz[i] = niz[i];
		v.push_back({siz[i], i});
		s[i].push_back(i); whs[i] = i;
		
		for (int tren : graph[i]) graph2[i].insert({niz[tren], tren});
	}
	sort(v.begin(), v.end());
	
	for (int i = 1; i <= n; i++) bio[i] = true;
	for (int i = 0; i < n; i++) {
		int node = v[i].second;
		int val = v[i].first;
		//printf("trying: %d\n", node);
		
		for (int tren : graph[node]) {
			if (niz[tren] <= val) {
				//printf("merging: %d %d\n", node, tren);
				merg(tren, node);
			}
		}
		
		int ac = fin(node);	
		if (!graph2[ac].empty() && graph2[ac].begin()->first > siz[ac]) {
			//printf("not able (%d %d) %d\n", graph2[ac].begin()->first, graph2[ac].begin()->second, siz[ac]);
			int ind = whs[ac];
			for (int iter : s[ind]) {
				bio[iter] = false;
			}
			s[ind].clear();
		}
	}
	for (int i = 1; i <= n; i++) printf("%d", bio[i]);
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:46:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  for (int i = 1; i <= n; i++) scanf("%d", niz+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", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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