oj.uz

답안 #230744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230744 2020-05-11T14:11:07 Z pavement Baloni (COCI15_baloni) C++17
100 / 100
 118 ms 38904 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef TEST
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define ins insert
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, T, link[1000005], sz[1000005];
vector<int> H[1000005];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

bool unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return 0;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
	return 1;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	T = N;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 1, tmp; i <= N; i++) {
		cin >> tmp;
		if (H[tmp + 1].size()) {
			T -= unite(i, H[tmp + 1].back());
			H[tmp + 1].ppb();
		}
		H[tmp].pb(i);
	}
	cout << T << '\n';
}

Compilation message

baloni.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 24064 KB Output is correct
5 Correct 110 ms 37500 KB Output is correct
6 Correct 118 ms 38904 KB Output is correct
7 Correct 96 ms 36344 KB Output is correct
8 Correct 97 ms 36216 KB Output is correct
9 Correct 108 ms 36856 KB Output is correct
10 Correct 107 ms 37524 KB Output is correct