oj.uz

Submission #578268

# Submission time Handle Problem Language Result Execution time Memory
578268 2022-06-16T09:46:24 Z kingfran1907 Stranded Far From Home (BOI22_island) C++14
0 / 100
 726 ms 75516 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;
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

island.cpp: In function 'int main()':
island.cpp:89:31: warning: format '%d' expects argument of type 'int', but argument 4 has type 'llint' {aka 'long long int'} [-Wformat=]
   89 |     printf("not able (%d %d) %d\n", graph2[ac].begin()->first, graph2[ac].begin()->second, siz[ac]);
      |                              ~^                                                            ~~~~~~~
      |                               |                                                                  |
      |                               int                                                                llint {aka long long int}
      |                              %lld
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
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19048 KB Output is correct
2 Incorrect 726 ms 75516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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