oj.uz

Submission #93334

# Submission time Handle Problem Language Result Execution time Memory
93334 2019-01-07T15:14:19 Z updown1 Sirni (COCI17_sirni) C++17
140 / 140
 4132 ms 578960 KB 
/*
https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/COCI/official/2017/contest6_solutions/solutions.pdf
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, MM = 10000001, INF=1000000000;
///500,000,000
int N, big, par[MAXN], siz[MAXN], go[MM], prea, prex, preadd;
ll out;
set<int> inp;
vector<int> vals;
vector< pair<int, int> > edges[MM]; /// [weight] = (n1, n2)

void make(int n1, int x, int add=0) {
    int a;
    if (x > big) a = N;
    else a = go[x];
    if (add == 0) {
        if (a != prea) {
            edges[vals[prea]-prex+preadd].emplace_back(n1, prea);
            //w<< "connecting" s n1+1 s prea+1 c vals[prea]-prex+preadd<<e;
        }
    }
    prea = a;
    prex = x;
    preadd = add;
}

int root (int x) {
    if (par[x] == x) return x;
    par[x] = root(par[x]);
    return par[x];
}
int join(int a, int b) {
    if (siz[a] > siz[b]) {
        /// push b into a
        siz[a] += siz[b];
        par[b] = a;
    }
    else {
        /// push a into b
        siz[b] += siz[a];
        par[a] = b;
    }
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	ffi {int a; cin >> a; inp.insert(a); par[i] = i; siz[i] = 1;}
	for (int i: inp) vals.pb(i); vals.pb(INF);
	big = vals[vals.size()-2];
	N = vals.size()-1;
	go[MM-1] = N;
	for (int i=MM-2; i>=0; i--) {
        go[i] = go[i+1];
        if (go[i+1] != 0 && i == vals[go[i+1]-1]) go[i]--;
	}
	ffi {
        int x = vals[i];
        make(i, x+1, 1);
        for (int j=x+x; j<=big+x; j+=x) {
            make(i, j);
        }
	}
	For (i, 0, MM) for (auto j: edges[i]) {
        int a = j.a, b = j.b;
        if (root(a) == root(b)) continue;
        out += i;
        join(par[a], par[b]); /// just called root so this should be fine
	}
	w<< out<<e;
}

Compilation message

sirni.cpp: In function 'int join(int, int)':
sirni.cpp:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sirni.cpp: At global scope:
sirni.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sirni.cpp: In function 'int main()':
sirni.cpp:66:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i: inp) vals.pb(i); vals.pb(INF);
  ^~~
sirni.cpp:66:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i: inp) vals.pb(i); vals.pb(INF);
                               ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 274552 KB Output is correct
2 Correct 422 ms 276856 KB Output is correct
3 Correct 300 ms 274760 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 274488 KB Output is correct
2 Correct 1218 ms 275080 KB Output is correct
3 Correct 288 ms 274680 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 274680 KB Output is correct
2 Correct 292 ms 274424 KB Output is correct
3 Correct 295 ms 274616 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 289656 KB Output is correct
2 Correct 466 ms 316072 KB Output is correct
3 Correct 406 ms 293600 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 276728 KB Output is correct
2 Correct 356 ms 297536 KB Output is correct
3 Correct 327 ms 288604 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 301568 KB Output is correct
2 Correct 522 ms 331192 KB Output is correct
3 Correct 430 ms 292712 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 279748 KB Output is correct
2 Correct 515 ms 324576 KB Output is correct
3 Correct 405 ms 292116 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 292336 KB Output is correct
2 Correct 2858 ms 487600 KB Output is correct
3 Correct 477 ms 295508 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 292588 KB Output is correct
2 Correct 3873 ms 578960 KB Output is correct
3 Correct 508 ms 299052 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 277744 KB Output is correct
2 Correct 4132 ms 573572 KB Output is correct
3 Correct 345 ms 294632 KB Output is correct