oj.uz

답안 #578260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578260 2022-06-16T09:34:35 Z kingfran1907 Stranded Far From Home (BOI22_island) C++14
0 / 100
 723 ms 87512 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) {
	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;
		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);
				}
			}
		}
		
		for (int node : ts) {
			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:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:48:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  for (int i = 1; i <= n; i++) scanf("%d", niz+i);
      |                               ~~~~~^~~~~~~~~~~~~
island.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Incorrect 13 ms 19572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19052 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 371 ms 70252 KB Output is correct
4 Correct 206 ms 41408 KB Output is correct
5 Correct 400 ms 70128 KB Output is correct
6 Incorrect 394 ms 66568 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19028 KB Output is correct
2 Incorrect 723 ms 87512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19116 KB Output is correct
2 Incorrect 491 ms 52056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Incorrect 13 ms 19572 KB Output isn't correct
5 Halted 0 ms 0 KB -