oj.uz

Submission #126464

# Submission time Handle Problem Language Result Execution time Memory
126464 2019-07-07T19:39:52 Z letrongdat Sirni (COCI17_sirni) C++17
112 / 140
 5000 ms 574064 KB 
#include <bits/stdc++.h>
using namespace std;
#define forn(i, a, b)               for(int i=a; i<=b; ++i)
#define ford(i, a ,b)               for(int i=a; i>=b; --i)
#define repn(i, a, b)               for(int i=a; i <b; ++i)
typedef pair<int, int> ii;
const int maxM = 1e7+ 10;
const int maxN = 1e5 +10;
int N;
int Near[maxM];
int lab[maxN];
vector<int> P;
vector<ii> Edge[maxM];
int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}
bool join(int u, int v) {
    int l1 = root(u), l2 = root(v);
    if (l1 == l2) return false;
    if (lab[l1] > lab[l2]) swap(l1, l2);
    lab[l1] += lab[l2];
    lab[l2] = l1;
    return true;
}
int main() {
// #ifndef ONLINE_JUDGE
//     freopen("a.inp", "r", stdin);
// #endif // ONLINE_JUDGE
    ios::sync_with_stdio(0);
    memset(lab, -1, sizeof lab);
    cin >> N;
    P.resize(N);
    repn(i, 0, N) cin >> P[i];
    sort(P.begin(), P.end());
    P.resize(unique(P.begin(), P.end()) - P.begin());
    memset(Near, 0x3f, sizeof Near);
    repn(i, 0, P.size()) Near[P[i]] = i;
    ford(i, P.back(), 0) Near[i] = min(Near[i], Near[i+1]);
    repn(i, 0, P.size() -1) {
        int weight = P[Near[P[i]+1]] - P[i];
        if (weight < P[i]) Edge[weight].push_back({i, Near[P[i]+1]});
        for(int j = 2*P[i]; j <= P.back(); j += P[i]) {
            int weight = P[Near[j]] - j;
            if (weight < P[i]) Edge[weight].push_back({i, Near[j]});
        }
    }
    long long result = 0, cnt = 0;
    repn(i, 0, maxM) {
        for(auto &e: Edge[i]) if (join(e.first, e.second)) {
            result += i;
            cnt ++;
            if (cnt == P.size() -1) break;
        }
    }
    cout << result;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:5:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define repn(i, a, b)               for(int i=a; i <b; ++i)
sirni.cpp:38:10:
     repn(i, 0, P.size()) Near[P[i]] = i;
          ~~~~~~~~~~~~~~                             
sirni.cpp:38:5: note: in expansion of macro 'repn'
     repn(i, 0, P.size()) Near[P[i]] = i;
     ^~~~
sirni.cpp:5:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define repn(i, a, b)               for(int i=a; i <b; ++i)
sirni.cpp:40:10:
     repn(i, 0, P.size() -1) {
          ~~~~~~~~~~~~~~~~~                          
sirni.cpp:40:5: note: in expansion of macro 'repn'
     repn(i, 0, P.size() -1) {
     ^~~~
sirni.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (cnt == P.size() -1) break;
                 ~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 274920 KB Output is correct
2 Correct 360 ms 277112 KB Output is correct
3 Correct 309 ms 275064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 274780 KB Output is correct
2 Correct 682 ms 275700 KB Output is correct
3 Correct 330 ms 274936 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 274848 KB Output is correct
2 Correct 341 ms 274800 KB Output is correct
3 Correct 314 ms 275008 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 284612 KB Output is correct
2 Correct 590 ms 311780 KB Output is correct
3 Correct 400 ms 289924 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 276456 KB Output is correct
2 Correct 521 ms 297056 KB Output is correct
3 Correct 364 ms 284608 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 297012 KB Output is correct
2 Correct 715 ms 326688 KB Output is correct
3 Correct 396 ms 288256 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 278284 KB Output is correct
2 Correct 634 ms 320896 KB Output is correct
3 Correct 434 ms 288140 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 287284 KB Output is correct
2 Correct 3589 ms 482636 KB Output is correct
3 Correct 546 ms 289784 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 287052 KB Output is correct
2 Execution timed out 5047 ms 574064 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 277112 KB Output is correct
2 Execution timed out 5138 ms 560400 KB Time limit exceeded
3 Halted 0 ms 0 KB -