oj.uz

Submission #575100

# Submission time Handle Problem Language Result Execution time Memory
575100 2022-06-09T16:57:55 Z Sorting Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 415800 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 500 + 3;
const int M = 1e5 + 3;
const int Q = 1e6 + 3;
const int INF = 1e9;

int n, m, q;
array<ll, 3> e[M];
ll x[Q];

struct DSU{
    int sz[N], par[N];

    void init(int n){
        for(int i = 1; i <= n; ++i)
            sz[i] = 1, par[i] = i;
    }

    int getP(int x){
        if(par[x] == x) return x;
        return par[x] = getP(par[x]);
    }

    bool unite(int a, int b){
        a = getP(a), b = getP(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
        return true;
    }
} dsu;

vector<int> pr[M], su[M];

pair<ll, int> get_ans(const vector<int> &e1, const vector<int> &e2, ll x, int ptr){
    ll ans = 0;
    int cnt = 0;

    vector<pair<int, int>> e3;
    int ptr1 = 0, ptr2 = 0;
    while(ptr1 != e1.size() && ptr2 != e2.size()){
        int cost1 = x - e[e1[ptr1]][0];
        int cost2 = e[e2[ptr2]][0] - x;

        if(cost1 < cost2)
            e3.push_back({cost1, e1[ptr1++]});
        else
            e3.push_back({cost2, e2[ptr2++]});
    }
    while(ptr1 != e1.size()){
        int cost1 = x - e[e1[ptr1]][0];
        e3.push_back({cost1, e1[ptr1++]});
    }
    while(ptr2 != e2.size()){
        int cost2 = e[e2[ptr2]][0] - x;
        e3.push_back({cost2, e2[ptr2++]});
    }
    
    dsu.init(n);
    for(auto [cost, idx]: e3){
        if(dsu.unite(e[idx][1], e[idx][2])){
            ans += cost;
            if(idx >= ptr)
                ++cnt;
        }
    }

    return {ans, cnt};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        cin >> e[i][1] >> e[i][2] >> e[i][0];
    }
    sort(e, e + m);

    pr[0] = {0};
    for(int i = 1; i < m; ++i){
        dsu.init(n);
        pr[i].push_back(i);
        for(int idx: pr[i - 1])
            if(dsu.unite(e[idx][1], e[idx][2]))
                pr[i].push_back(idx);
    }

    su[m - 1] = {m - 1};
    for(int i = m - 2; i >= 0; --i){
        dsu.init(n);
        su[i].push_back(i);
        for(int idx: su[i + 1])
            if(dsu.unite(e[idx][1], e[idx][2]))
                su[i].push_back(idx);
    }

    ll ans = 0, cnt = 0, prevx = -INF, next_change;
    auto p = get_ans({}, su[0], prevx, 0);
    ans = p.first;
    cnt = p.second;

    int ptr = 0;
    cin >> q;
    for(int i = 0; i < q; ++i){
        cin >> x[i];
        while(ptr != m && x[i] >= e[ptr][0])
            ++ptr;

        vector<int> e1;
        if(0 <= ptr - 1){
            e1 = pr[ptr - 1];
        }
        vector<int> e2;
        if(ptr <= m - 1){
            e2 = su[ptr];
        }

        auto p = get_ans(e1, e2, x[i], ptr);
        ans = p.first;
        cnt = p.second;

        cout << ans << "\n";
    }
}

Compilation message

reconstruction.cpp: In function 'std::pair<long long int, int> get_ans(const std::vector<int>&, const std::vector<int>&, ll, int)':
reconstruction.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while(ptr1 != e1.size() && ptr2 != e2.size()){
      |           ~~~~~^~~~~~~~~~~~
reconstruction.cpp:50:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while(ptr1 != e1.size() && ptr2 != e2.size()){
      |                                ~~~~~^~~~~~~~~~~~
reconstruction.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     while(ptr1 != e1.size()){
      |           ~~~~~^~~~~~~~~~~~
reconstruction.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(ptr2 != e2.size()){
      |           ~~~~~^~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:108:17: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
  108 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                 ^~~
reconstruction.cpp:108:40: warning: unused variable 'next_change' [-Wunused-variable]
  108 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                                        ^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2079 ms 412364 KB Output is correct
21 Correct 1924 ms 412108 KB Output is correct
22 Correct 2011 ms 412220 KB Output is correct
23 Correct 2008 ms 412040 KB Output is correct
24 Correct 2021 ms 412276 KB Output is correct
25 Correct 2074 ms 412380 KB Output is correct
26 Correct 2064 ms 412448 KB Output is correct
27 Correct 2048 ms 412236 KB Output is correct
28 Correct 2062 ms 412604 KB Output is correct
29 Correct 1914 ms 409228 KB Output is correct
30 Correct 2055 ms 412352 KB Output is correct
31 Correct 2053 ms 412468 KB Output is correct
32 Correct 2089 ms 412492 KB Output is correct
33 Correct 2092 ms 412388 KB Output is correct
34 Correct 1549 ms 382824 KB Output is correct
35 Correct 2060 ms 412364 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Execution timed out 5089 ms 415800 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Execution timed out 5043 ms 17068 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2079 ms 412364 KB Output is correct
21 Correct 1924 ms 412108 KB Output is correct
22 Correct 2011 ms 412220 KB Output is correct
23 Correct 2008 ms 412040 KB Output is correct
24 Correct 2021 ms 412276 KB Output is correct
25 Correct 2074 ms 412380 KB Output is correct
26 Correct 2064 ms 412448 KB Output is correct
27 Correct 2048 ms 412236 KB Output is correct
28 Correct 2062 ms 412604 KB Output is correct
29 Correct 1914 ms 409228 KB Output is correct
30 Correct 2055 ms 412352 KB Output is correct
31 Correct 2053 ms 412468 KB Output is correct
32 Correct 2089 ms 412492 KB Output is correct
33 Correct 2092 ms 412388 KB Output is correct
34 Correct 1549 ms 382824 KB Output is correct
35 Correct 2060 ms 412364 KB Output is correct
36 Correct 2605 ms 412860 KB Output is correct
37 Correct 2413 ms 412760 KB Output is correct
38 Correct 2547 ms 412584 KB Output is correct
39 Correct 2568 ms 412596 KB Output is correct
40 Correct 2646 ms 412900 KB Output is correct
41 Correct 2719 ms 412880 KB Output is correct
42 Correct 2776 ms 412940 KB Output is correct
43 Correct 2709 ms 412888 KB Output is correct
44 Correct 2614 ms 412808 KB Output is correct
45 Correct 2248 ms 410016 KB Output is correct
46 Correct 2563 ms 412860 KB Output is correct
47 Correct 2682 ms 412868 KB Output is correct
48 Correct 2782 ms 412812 KB Output is correct
49 Correct 2775 ms 412860 KB Output is correct
50 Correct 1869 ms 383340 KB Output is correct
51 Correct 2646 ms 412876 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2079 ms 412364 KB Output is correct
21 Correct 1924 ms 412108 KB Output is correct
22 Correct 2011 ms 412220 KB Output is correct
23 Correct 2008 ms 412040 KB Output is correct
24 Correct 2021 ms 412276 KB Output is correct
25 Correct 2074 ms 412380 KB Output is correct
26 Correct 2064 ms 412448 KB Output is correct
27 Correct 2048 ms 412236 KB Output is correct
28 Correct 2062 ms 412604 KB Output is correct
29 Correct 1914 ms 409228 KB Output is correct
30 Correct 2055 ms 412352 KB Output is correct
31 Correct 2053 ms 412468 KB Output is correct
32 Correct 2089 ms 412492 KB Output is correct
33 Correct 2092 ms 412388 KB Output is correct
34 Correct 1549 ms 382824 KB Output is correct
35 Correct 2060 ms 412364 KB Output is correct
36 Correct 3 ms 5024 KB Output is correct
37 Correct 3 ms 4948 KB Output is correct
38 Correct 3 ms 4948 KB Output is correct
39 Execution timed out 5089 ms 415800 KB Time limit exceeded
40 Halted 0 ms 0 KB -