oj.uz

Submission #578245

# Submission time Handle Problem Language Result Execution time Memory
578245 2022-06-16T09:15:33 Z kingfran1907 Stranded Far From Home (BOI22_island) C++14
0 / 100
 440 ms 65780 KB 
#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;

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]) 
			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 (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()) 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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19124 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Incorrect 12 ms 19360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19116 KB Output is correct
2 Correct 9 ms 18992 KB Output is correct
3 Correct 239 ms 48352 KB Output is correct
4 Correct 182 ms 37684 KB Output is correct
5 Correct 340 ms 48836 KB Output is correct
6 Incorrect 291 ms 49720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 440 ms 65780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 439 ms 52448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19124 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Incorrect 12 ms 19360 KB Output isn't correct
5 Halted 0 ms 0 KB -