oj.uz

Submission #714060

# Submission time Handle Problem Language Result Execution time Memory
714060 2023-03-23T18:31:51 Z si_jo Sirni (COCI17_sirni) C++14
84 / 140
 2682 ms 786432 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
 
#define ll              long long
#define int				ll
#define pb              push_back
#define ppb             pop_back
#define pf              push_front
#define ppf             pop_front
#define all(x)          (x).begin(), (x).end()
#define uniq(v)         (v).erase(unique(all(v)), (v).end())
#define sz(x)           (int)((x).size())
#define fr              first
#define sc              second
#define vi              vector<int>
#define vvi				vector<vi>
#define pii             pair<int, int>
#define rep(i,a,b)      for(int i = a; i < b; i++)
#define irep(i, a, b)   for(int i = a; i > b; i--)
#define mem1(a)         memset(a, -1, sizeof(a))
#define mem0(a)         memset(a, 0, sizeof(a))
#define clz             __builtin_clzll			//leading zeroes
#define ctz             __builtin_ctzll			//trailing zeroes
#define ppc             __builtin_popcountll
#define nl				cout << '\n'
 
template<typename T>
istream &operator>>(istream &in, vector<T>& v){
    for(int i = 0; i < v.size(); i++)
        in >> v[i];
    return in;
}
template<typename T>
ostream &operator<<(ostream &out, vector<T>& v){
    for(int i = 0; i < v.size(); i++)
        out << v[i] << " ";
    return out;
}
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& p){ in >> p.fr >> p.sc; return in; }
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2>& p){ out << p.fr << " " << p.sc << " "; return out; }
 
const ll INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;
const int MAX = numeric_limits<int>::max();
const int MIN = numeric_limits<int>::min();
 
const int N = 0;
 
int egcd(int a, int b, int& x, int& y, int mod){
	if(b == 0){
		x = 1, y = 0;
		return a;
	}
	int x1, y1, g = egcd(b, a % b, x1, y1, mod);
	x = y1 % mod, y = ((x1 - (a / b)*y1) % mod + mod) % mod;
	return g;
}
 
int root(int x, vi& par){
	while(x != par[x]){
		par[x] = par[par[x]];
		x = par[x];
	}
	return x;
}
 
bool merge(int u, int v, vi& par, vi& s){
	int x = root(u, par), y = root(v, par);
	if(x == y)	return 0;
	if(s[x] < s[y])	swap(x, y);
	s[x] += s[y];
	par[y] = x;
	return 1;
}
 
void solve(){
	ll n, cst = 0; cin >> n;
	vi v(n); cin >> v;
	sort(all(v)); uniq(v); n = sz(v);
	vector<array<int, 3>> e;
	rep(i, 0, n){
		if(i + 1 < n)	e.pb({v[i + 1] - v[i], i + 1, i});
		for(int j = 2*v[i]; j <= 1e7; j += v[i]){
			auto it = lower_bound(all(v), j);
			if(it != v.end())	e.pb({*it - j, it - v.begin(), i});
		}
	}
	sort(all(e));
	vi par(n), s(n, 1);
	rep(i, 0, n)	par[i] = i;
	for(auto [w, u, v] : e)	if(merge(u, v, par, s))	cst += w;
	cout << cst; nl;
}
 
signed main(){
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1; //cin >> t;
	rep(i, 0, t){
		solve();
	}
}

Compilation message

sirni.cpp: In function 'void solve()':
sirni.cpp:98:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for(auto [w, u, v] : e) if(merge(u, v, par, s)) cst += w;
      |           ^
sirni.cpp: In instantiation of 'std::istream& operator>>(std::istream&, std::vector<_Tp>&) [with T = long long int; std::istream = std::basic_istream<char>]':
sirni.cpp:85:18:   required from here
sirni.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 542 ms 98868 KB Output is correct
3 Correct 4 ms 1232 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 620 KB Output is correct
2 Runtime error 822 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 788 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 51196 KB Output is correct
2 Correct 1925 ms 101344 KB Output is correct
3 Correct 926 ms 100288 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6712 KB Output is correct
2 Correct 847 ms 100192 KB Output is correct
3 Correct 677 ms 50928 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1114 ms 100336 KB Output is correct
2 Correct 2603 ms 198840 KB Output is correct
3 Correct 832 ms 51188 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 13264 KB Output is correct
2 Correct 2682 ms 198832 KB Output is correct
3 Correct 858 ms 51080 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 51212 KB Output is correct
2 Runtime error 891 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 51224 KB Output is correct
2 Runtime error 860 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6848 KB Output is correct
2 Runtime error 1262 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -