| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713563 |
2023-03-22T13:32:44 Z |
si_jo |
Sirni (COCI17_sirni) |
C++14 |
|
697 ms |
78752 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 = 1e6 + 1;
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;
}
class seg_tree{
private:
typedef struct node{
bool val;
}node;
int sz;
node nd;
vector<node> tree;
void combine(node& res, node& n1, node& n2){
res.val = n1.val|n2.val;
}
public:
void build(int n){
sz = n;
nd.val = 0;
while(ppc(sz) != 1) sz++;
tree.clear();
tree.assign(2*sz - 1, nd);
}
node query(int l, int r, int i = 0, int low = 0, int high = 1e9){
high = min(high, sz - 1);
if(l > high || r < low || l > r) return nd;
else if(l <= low && high <= r) return tree[i];
else{
node res = nd, n1 = query(l, r, 2*i + 1, low, (low + high) / 2), n2 = query(l, r, 2*i + 2, (low + high) / 2 + 1, high);
combine(res, n1, n2);
return res;
}
}
void upd(int pos){
int i = sz - 1 + pos;
tree[i].val = 1;
while(sz != 1){
i = (i - 1) / 2;
combine(tree[i], tree[2*i + 1], tree[2*i + 2]);
if(i == 0) break;
}
}
void pr(int n){
rep(i, 0, n) cout << tree[i + sz - 1].val << " "; nl;
}
};
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 unopt(int n, vi& v){
vi par(n), s(n);
vector<array<int, 3>> e;
rep(i, 0, n) rep(j, 0, n) if(i != j) e.pb({min(v[i] % v[j], v[j] % v[i]), i, j});
sort(all(e));
rep(i, 0, n) par[i] = i;
int cst = 0;
for(auto [w, u, v] : e) if(merge(u, v, par, s)) cst += w;
cout << cst; nl;
}
vvi dp(N);
vi par(N), s(N);
void solve(){
ll n, cst = 0; cin >> n;
vi v(n); cin >> v;
if(n <= 1e3){
unopt(n, v); return;
}
seg_tree pos;
pos.build(N);
sort(all(v)); uniq(v);
vector<array<int, 3>> e;
for(int i : v){
//determine the nearest position x to the left st. sz(dp) > 0 and add edges between i and each element in dp[x]
if(i != v[0]){
int l = v[0], h = i, a;
while(l <= h){
int k = l + h >> 1;
if(pos.query(k, i).val) a = k, l = k + 1;
else h = k - 1;
}
for(int j : dp[a]) e.pb({i - a, i, j});
}
if(sz(dp[i]) == 0) for(int j = i; j < N; j += i){
dp[j].pb(i);
if(sz(dp[j]) == 1) pos.upd(j);
}
}
sort(all(e));
rep(i, 1, 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 unopt(int, std::vector<int>&)':
sirni.cpp:139:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
139 | for(auto [w, u, v] : e) if(merge(u, v, par, s)) cst += w;
| ^
sirni.cpp: In function 'void solve()':
sirni.cpp:160:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
160 | int k = l + h >> 1;
| ~~^~~
sirni.cpp:173:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
173 | 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 = int; std::istream = std::basic_istream<char>]':
sirni.cpp:147:18: required from here
sirni.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
sirni.cpp:164:31: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
164 | for(int j : dp[a]) e.pb({i - a, i, j});
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
44096 KB |
Output is correct |
| 2 |
Correct |
162 ms |
44040 KB |
Output is correct |
| 3 |
Correct |
152 ms |
44072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
44044 KB |
Output is correct |
| 2 |
Correct |
182 ms |
44088 KB |
Output is correct |
| 3 |
Correct |
150 ms |
44088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
44088 KB |
Output is correct |
| 2 |
Correct |
131 ms |
44056 KB |
Output is correct |
| 3 |
Correct |
160 ms |
44016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
587 ms |
53324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
38740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
697 ms |
57968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
349 ms |
54728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
120 ms |
76364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
78752 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
69392 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
