oj.uz

답안 #872670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872670 2023-11-13T14:08:57 Z ace_in_the_hole Sirni (COCI17_sirni) C++17
98 / 140
 5000 ms 441008 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define cst(T) const T&

template<class A, class B> bool umin(A& var, cst(B) val) {
	return (val < var) ? (var = val, true) : false;
}
template<class A, class B> bool umax(A& var, cst(B) val) {
	return (var < val) ? (var = val, true) : false;
}

typedef long long Int;
typedef long double Real;
const int MOD = 2004010501;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> Int random(const X& l, const Y& r) {
	return uniform_int_distribution<Int>(l,r)(rng);
}
#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';

const int N = 1e5 + 50;
const int V = 1e7 + 10;
const int INF = 1e9;

int v2pos[V];

class DisjointSet {
private :
	int size; int* label = nullptr;
public :
	DisjointSet(int size) : size(size) {
		if (label != nullptr) delete label;
		label = new int[size + 1];
		for (int i = 0; i <= size; i++) label[i] = -1;
	}
  	
	int find_root(int u) {
		if (label[u] < 0) return u;
		return label[u] = find_root(label[u]);
	}
  
	bool merge_set(int u, int v) {
    	u = find_root(u), v = find_root(v);
		if (u == v) return false;
		if (-(label[u]) < -(label[v])) swap(u,v);
		return label[u] += label[v], label[v] = u, true;
	}
  	
  	bool same_set(int a, int b) { 
		return find_root(a) == find_root(b);
	}
}; 

struct Edge {
	int u,v,w;
	bool operator< (cst(Edge) rhs) const {
		return w > rhs.w;
	}
};

void solve(int testID) {
	// DBGn(testID);
	int n;
	cin >> n;
	vector<int> p(n);
	for (auto &pi : p) cin >> pi;
	sort(all(p));
	p.resize(unique(all(p)) - begin(p));
	n = int(size(p));
	for (int i = 0; i < n; i++) v2pos[p[i]] = i;
	priority_queue<Edge> edges;
	set<int> values(all(p));
	auto find_edges = [&] (int a, int threshold = 0) {
		if (!values.empty()) {
			int mq = max(0, threshold / a) + 1;
			do {
				auto it = values.lower_bound(mq * a);
				if (it == end(values)) break;
				edges.push({a,*it, (*it) % a});
				mq = (*it) / a + 1;
			} while (1);
		}
	};
	for (auto p_i : p) {
		values.erase(p_i);
		find_edges(p_i);
	}
	DisjointSet dsu(n);
	Int ans = 0;
	while (!edges.empty()) {
		auto [u,v,w] = edges.top(); edges.pop();
		u = v2pos[u], v = v2pos[v];
		if (dsu.merge_set(u,v)) ans += w;
	}
	cout << ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	#define task "WF"
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	int numTests = 1;
	// cin >> numTests;
	for (int i = 1; i <= numTests; i++) solve(i);
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:113:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 37724 KB Output is correct
2 Correct 38 ms 41428 KB Output is correct
3 Correct 7 ms 37916 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 14 ms 36444 KB Output is correct
3 Correct 6 ms 37980 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37724 KB Output is correct
2 Correct 4 ms 29276 KB Output is correct
3 Correct 6 ms 37724 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 296 ms 24680 KB Output is correct
2 Correct 975 ms 59960 KB Output is correct
3 Correct 345 ms 34740 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 9672 KB Output is correct
2 Correct 493 ms 57288 KB Output is correct
3 Correct 256 ms 21276 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 644 ms 59764 KB Output is correct
2 Correct 1323 ms 109784 KB Output is correct
3 Correct 337 ms 35032 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 11460 KB Output is correct
2 Correct 1380 ms 108984 KB Output is correct
3 Correct 314 ms 35964 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 403 ms 71072 KB Output is correct
2 Execution timed out 5012 ms 441008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 71340 KB Output is correct
2 Execution timed out 5031 ms 439684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 44492 KB Output is correct
2 Execution timed out 5073 ms 437676 KB Time limit exceeded
3 Halted 0 ms 0 KB -