oj.uz

Submission #547288

# Submission time Handle Problem Language Result Execution time Memory
547288 2022-04-10T09:11:41 Z AA_Surely Sirni (COCI17_sirni) C++17
140 / 140
 3265 ms 434116 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 1e5 + 7;
const int A = 1e7 + 7;

struct Edge {
    int u, v, w;

    inline bool operator < (const Edge other) {
        return w < other.w;
    }
} x;

int n, era[A];
int par[N];
vector<Edge> eset;

int grand(int x) {
    if (par[x] < 0) return x;
    return par[x] = grand(par[x]);
}

inline bool merge(int a, int b) {
    a = grand(a); b = grand(b);
    if (a == b) return 0;

    if (par[a] > par[b]) swap(a, b);
    par[a] += par[b];
    par[b] = a;

    return 1;
}

int main() {
    IOS;

    fill(era, era + A, -1);
    
    cin >> n;
    VI ns(n);
    F0R(i, n) cin >> ns[i];

    sort(ALL(ns));
    ns.resize(unique(ALL(ns)) - ns.begin());
    n = ns.size();

    F0R(i, n) era[ ns[i] ] = i;
    R0F(i, A - 1) if (era[i] == -1)
        era[i] = era[i + 1];
    
    F0R(i, n) for(int j = ns[i]; j < A; j += ns[i]) if (era[j] != -1) {
        if (j + ns[i] >= A || era[j + ns[i]] != era[j]) {
            x.u = i; x.v = era[j];
            x.w = ns[ era[j] ] - j;
            eset.pb(x);
        }

        if ((era[j + 1] != -1 && era[j + 1] != era[j]) && (j + ns[i] >= A || era[j + ns[i]] != era[j + 1])) {
            x.u = i; x.v = era[j + 1];
            x.w = ns[ era[j + 1] ] - j;
            eset.pb(x);
        }
    }

    sort(ALL(eset));
    fill(par, par + n, -1);
    
    LL ans = 0;
    F0R(i, eset.size()) if (merge(eset[i].u, eset[i].v)) ans += eset[i].w;
    cout << ans << endl;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:3:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n)  for(int i=x; i<n; i++)
      |                                   ^
sirni.cpp:4:19: note: in expansion of macro 'FOR'
    4 | #define F0R(i,n)  FOR(i,0,n)
      |                   ^~~
sirni.cpp:95:5: note: in expansion of macro 'F0R'
   95 |     F0R(i, eset.size()) if (merge(eset[i].u, eset[i].v)) ans += eset[i].w;
      |     ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 39500 KB Output is correct
2 Correct 110 ms 42636 KB Output is correct
3 Correct 42 ms 39708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 39696 KB Output is correct
2 Correct 337 ms 41104 KB Output is correct
3 Correct 44 ms 39756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 39576 KB Output is correct
2 Correct 40 ms 39460 KB Output is correct
3 Correct 41 ms 39712 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 64572 KB Output is correct
2 Correct 611 ms 138344 KB Output is correct
3 Correct 252 ms 64516 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 42696 KB Output is correct
2 Correct 435 ms 89224 KB Output is correct
3 Correct 276 ms 64536 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 89188 KB Output is correct
2 Correct 764 ms 138448 KB Output is correct
3 Correct 241 ms 64568 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 45860 KB Output is correct
2 Correct 751 ms 138488 KB Output is correct
3 Correct 240 ms 64524 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 64548 KB Output is correct
2 Correct 2149 ms 433940 KB Output is correct
3 Correct 184 ms 65312 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 64592 KB Output is correct
2 Correct 3123 ms 434116 KB Output is correct
3 Correct 238 ms 65384 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 42712 KB Output is correct
2 Correct 3265 ms 433992 KB Output is correct
3 Correct 280 ms 65196 KB Output is correct