Submission #1281655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281655		rexdino	Sirni (COCI17_sirni)	C++20	14 / 140	1444 ms	851968 KiB

sirni

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define REP(i,a,b) for(int i=(a); i>=(b); --i)
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define sz(v) (int)(v).size()
#define ALL(v) (v).begin(),(v).end()
#define printArr(a, n) for (int i=1; i<=n; ++i) cout << a[i] << " "; el;
#define el cout << "\n"
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 1e7 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const ll INF = 1e18;

/// REXDINO FROM LTV HSGS ///
int n, m;
pii p[100005];
int par[100005];
int mx = 0;
vector<pii> cnt[N];
int last[N];
ll ans = 0;


int Find(int u){
    return par[u] < 0 ? u : par[u] = Find(par[u]);
}

bool join(int u, int v){
    u = Find(u); v = Find(v);
    if (u == v) return 0;
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
    return 1;
}

struct Edge{
    int u, v, w;
    bool operator < (const Edge &other) const {
        return w < other.w;
    }
};

vector<Edge> edges;

void solve(){
    cin >> n;
    FOR(i, 1, n) par[i] = -1;
    FOR(i, 1, n){
        int x;
        cin >> x;
        if (last[x] != 0){
            join(last[x], i);
        } else {
            last[x] = i;
            p[++m] = {x, i};
        }
    }

    sort(p + 1, p + m + 1);
    mx = p[m].fi;


    FOR(i, 1, m){
        for (int j = 1; 1ll * p[i].fi * j <= mx; ++j){
            int x = lower_bound(p + 1, p + m + 1, make_pair(p[i].fi * j + (j == 1), 0)) - p;
//            cout << i << " " << j << " " << x << " " << p[x].fi, el;
            if (x <= m) edges.push_back({p[i].se, p[x].se, p[x].fi % p[i].fi});
        }
    }

    for (Edge T : edges) cnt[T.w].push_back(make_pair(T.u, T.v));
    FOR(i, 0, mx){
        FOR(j, 0, sz(cnt[i]) - 1){
            if (join(cnt[i][j].fi, cnt[i][j].se)){
                ans += i;
            }
        }
    }


    cout << ans;
}

signed main(){
    #define NAME "main"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--) solve();

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14