oj.uz

답안 #93313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93313 2019-01-07T14:32:46 Z updown1 Sirni (COCI17_sirni) C++17
98 / 140
 5000 ms 400696 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 endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, INF=1000000000;
///500,000,000
int N, big, par[MAXN], siz[MAXN], pre;
ll out;
set<int> inp;
vector<int> vals;
vector<pair<int, pair<int, int> > > edges; /// (weight, (n1, n2))

void make(int n1, int x, int add=0) {
    int a = pre, b=N+1;
    while (a != b) {
        int mid = (a+b)/2;
        if (vals[mid] >= x) b = mid;
        else a = mid+1;
    }
    pre = a;
    if (vals[a] == INF) return;
    if (edges.size() > 0 && edges.back().b.a == n1 && edges.back().b.b == a) {
        edges[edges.size()-1] = mp(vals[a]-x+add, mp(n1, a));
    }
    else edges.pb(mp(vals[a]-x+add, mp(n1, a)));
    //w<< "connecting" s n1+1 s a+1 s x c vals[a]-x+add<<e;
}

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;
	ffi {
	    pre = 0;
        int x = vals[i];
        make(i, x+1, 1);
        for (int j=x+x; j<=big; j+=x) {
            make(i, j);
        }
	}
	sort(edges.begin(), edges.end());
	for (auto i: edges) {
        int cost = i.a, a = i.b.a, b = i.b.b;
        if (root(a) == root(b)) continue;
        out += cost;
        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:60:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sirni.cpp: At global scope:
sirni.cpp:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sirni.cpp: In function 'int main()':
sirni.cpp:67:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i: inp) vals.pb(i); vals.pb(INF);
  ^~~
sirni.cpp:67: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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 81 ms 3688 KB Output is correct
3 Correct 4 ms 760 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 564 ms 1664 KB Output is correct
3 Correct 4 ms 700 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 18664 KB Output is correct
2 Correct 930 ms 55144 KB Output is correct
3 Correct 389 ms 30152 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4508 KB Output is correct
2 Correct 425 ms 51292 KB Output is correct
3 Correct 272 ms 17872 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 618 ms 55672 KB Output is correct
2 Correct 1187 ms 104820 KB Output is correct
3 Correct 366 ms 30836 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 8676 KB Output is correct
2 Correct 1107 ms 103816 KB Output is correct
3 Correct 352 ms 30404 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 31176 KB Output is correct
2 Execution timed out 5109 ms 400696 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 31220 KB Output is correct
2 Execution timed out 5119 ms 399868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 4776 KB Output is correct
2 Execution timed out 5045 ms 399360 KB Time limit exceeded
3 Halted 0 ms 0 KB -