oj.uz

Submission #575112

# Submission time Handle Problem Language Result Execution time Memory
575112 2022-06-09T17:10:06 Z Sorting Reconstruction Project (JOI22_reconstruction) C++17
0 / 100
 5000 ms 401336 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;

int pr[M][N], su[M][N];

void try_dsu(DSU &dsu, int cost, int idx, ll &ans){
    if(dsu.unite(e[idx][1], e[idx][2])){
        ans += cost;
    }
}

ll get_ans(int *e1, int *e2, ll x, int ptr){
    ll ans = 0;
    int cnt = 0;

    int e1_sz = min(n - 1, ptr);
    int e2_sz = min(n - 1, m - ptr);

    dsu.init(n);

    int ptr1 = 0, ptr2 = 0;
    while(ptr1 != e1_sz && ptr2 != e2_sz){
        int cost1 = x - e[e1[ptr1]][0];
        int cost2 = e[e2[ptr2]][0] - x;

        if(cost1 < cost2)
            try_dsu(dsu, cost1, e1[ptr1++], ans);
        else
            try_dsu(dsu, cost2, e2[ptr2++], ans);
    }
    while(ptr1 != e1_sz){
        int cost1 = x - e[e1[ptr1]][0];
        try_dsu(dsu, cost1, e1[ptr1++], ans);
    }
    while(ptr2 != e2_sz){
        int cost2 = e[e2[ptr2]][0] - x;
        try_dsu(dsu, cost2, e2[ptr2++], ans);
    }

    return ans;
}

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] = 0;
    for(int i = 1; i < m; ++i){
        dsu.init(n);
        int cnt = 0;
        pr[i][cnt++] = i;

        int nxt_sz = min(i, n - 1);
        for(int j = 0; j < nxt_sz; ++j){
            int idx = pr[i - 1][j];
            if(dsu.unite(e[idx][1], e[idx][2]))
                pr[i][cnt++] = idx;
        }
    }

    su[m - 1][0] = m - 1;
    for(int i = m - 2; i >= 0; --i){
        dsu.init(n);
        int cnt = 0;
        su[i][cnt++] = i;

        int nxt_sz = min(n - 1, m - (i + 1));
        for(int j = 0; j < nxt_sz; ++j){
            int idx = su[i + 1][j];
            if(dsu.unite(e[idx][1], e[idx][2]))
                su[i][cnt++] = idx;
        }
    }

    ll ans = 0, cnt = 0, prevx = -INF, next_change;

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

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

        auto ans = get_ans(e1, e2, x[i], ptr);

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

Compilation message

reconstruction.cpp: In function 'll get_ans(int*, int*, ll, int)':
reconstruction.cpp:52:9: warning: unused variable 'cnt' [-Wunused-variable]
   52 |     int cnt = 0;
      |         ^~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:119:8: warning: unused variable 'ans' [-Wunused-variable]
  119 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |        ^~~
reconstruction.cpp:119:17: warning: unused variable 'cnt' [-Wunused-variable]
  119 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                 ^~~
reconstruction.cpp:119:26: warning: unused variable 'prevx' [-Wunused-variable]
  119 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                          ^~~~~
reconstruction.cpp:119:40: warning: unused variable 'next_change' [-Wunused-variable]
  119 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                                        ^~~~~~~~~~~
reconstruction.cpp:137:27: warning: 'e2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |         auto ans = get_ans(e1, e2, x[i], ptr);
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:137:27: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Execution timed out 5049 ms 401336 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -