Submission #578269

#	Time	Username	Problem	Language	Result	Execution time	Memory
578269		kingfran1907	Stranded Far From Home (BOI22_island)	C++14	100 / 100	798 ms	72324 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];
llint siz[maxn];
vector< int > s[maxn];
set< pair<int, int> > graph2[maxn];
int whs[maxn];
vector< pair<int, int> > v;
map< int, vector<int> > ms;

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

void merg(int a, int b, int val) {
	a = fin(a);
	b = fin(b);
	if (a == b) return;
	
	graph2[a].erase({niz[b], b});
	graph2[b].erase({niz[a], a});
	while (!graph2[a].empty() && graph2[a].begin()->first <= val) graph2[a].erase(graph2[a].begin());
	while (!graph2[b].empty() && graph2[b].begin()->first <= val) graph2[b].erase(graph2[b].begin());
	
	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;
		ms[niz[i]].push_back(i);
		
		for (int tren : graph[i]) 
			if (niz[tren] > niz[i]) graph2[i].insert({niz[tren], tren});
		//for (auto tren : graph2[i]) printf("%d ", tren.second); printf("\n");
	}
	sort(v.begin(), v.end());
	
	for (int i = 1; i <= n; i++) bio[i] = true;
	for (auto iter : ms) {
		vector< int > ts = iter.second;
		int val = iter.first;
		
		for (int node : ts) {
			for (int tren : graph[node]) {
				if (niz[tren] <= val) {
					merg(node, tren, val);
					//printf("merging: %d %d\n", node, tren);
				}
			}
		}
		
		for (int node : ts) {
			//printf("trying: %d\n", node);
			int ac = fin(node);	
			//if (!graph2[ac].empty()) printf("smallest neighbor: %d\n", graph2[ac].begin()->second);
			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:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:50:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  for (int i = 1; i <= n; i++) scanf("%d", niz+i);
      |                               ~~~~~^~~~~~~~~~~~~
island.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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