oj.uz

Submission #1038763

# Submission time Handle Problem Language Result Execution time Memory
1038763 2024-07-30T07:19:44 Z Phuoc Sirni (COCI17_sirni) C++14
42 / 140
 746 ms 786432 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set> 

using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = 998244353;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 200010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

int n, p[MAX];

void init(){
    cin >> n;
    FOR(i, 1, n) cin >> p[i];
}   

struct Dsu{
    int sz[MAX], par[MAX];
    Dsu(int _n = 0){
        FOR(i, 1, n){
            sz[i] = 1;
            par[i] = i;
        }
    }  

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

    bool Joint(int u, int v){
        u = Find(u); v = Find(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        return true;
    }
};

struct Edge{
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0){
        u = _u; v = _v; w = _w;
    }  
};

bool cmp(Edge &song, Edge &tuyen){
    return song.w < tuyen.w;
}

namespace subtask1{
    bool check(){
        return n <= 1000;
    }   

    vector <Edge> edges;

    int solve(){
        FOR(i, 1, n) FOR(j, 1, n) if(i != j) {
            edges.push_back(Edge(i, j, min(p[i] % p[j], p[j] % p[i])));
        }
        sort(edges.begin(), edges.end(), cmp);
        long long cost = 0;
        int numEdge = 0;
        Dsu dsu(n);
        for(Edge e : edges){
            if(dsu.Joint(e.u, e.v)){
                cost += 1LL * e.w;
                numEdge++;
                if(numEdge == n - 1) break;
            }
        }
        return cost;
    }
}

int solve(){
    if(subtask1::check()) return subtask1::solve();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    // freopen(test".inp", "r", stdin);
    // freopen(test".out", "w", stdout);
    srand(time(0));
    int t = 1;
    while(t--){
        init();
        cout << solve();
    }
    
    return 0;
}


 
/*** ROAD TO VOI 2025 ***/

Compilation message

sirni.cpp: In function 'int solve()':
sirni.cpp:127:1: warning: control reaches end of non-void function [-Wreturn-type]
  127 | }
      | ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 14492 KB Output is correct
2 Correct 102 ms 14280 KB Output is correct
3 Correct 121 ms 14276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14280 KB Output is correct
2 Correct 71 ms 14280 KB Output is correct
3 Correct 108 ms 14280 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 14280 KB Output is correct
2 Correct 92 ms 14280 KB Output is correct
3 Correct 126 ms 14276 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 746 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 745 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 688 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 740 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 721 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 710 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 707 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -