oj.uz

Submission #1115114

# Submission time Handle Problem Language Result Execution time Memory
1115114 2024-11-20T04:28:06 Z VinhLuu Reconstruction Project (JOI22_reconstruction) C++17
7 / 100
 5000 ms 136208 KB 
#include <bits/stdc++.h>
#define all(vin) vin.begin(), vin.end()
#define ll long long
using namespace std;

const int N = 1e6 + 5;

int n, m, q, _x[N], _y[N], _c[N], A[N];

namespace sub4{

  int pa[N], sz[N];
  int fin(int u){
    return pa[u] == u ? u : pa[u] = fin(pa[u]);
  }

  bool dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return 0;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    pa[v] = u;
    return 1;
  }

  int le[N], ri[N], pt[N];
  ll kq[N];
  vector<int> rrh;

  void solve(){

    for(int i = 1; i <= m; i ++) rrh.push_back(_c[i]);
    sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());

    for(int k = 1; k <= (int)rrh.size(); k ++){
      int tmp = rrh[k - 1];
      pt[k] = rrh[k - 1];
      vector<pair<int,int>> edge;
      ll ans = 0;
      for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
      for(int i = 1; i <= m; i ++){
         edge.push_back({abs(_c[i] - tmp), i});
      }
      sort(all(edge));
      for(auto [wt, id] : edge){
        if(dsu(_x[id], _y[id])){
          le[k] += (_c[id] <= tmp);
          ri[k] += (_c[id] >= tmp);
          kq[k] += wt;
//          cerr << id << " " << _x[id] << " " << _y[id] << " " << _c[id] << " r\n";
        }
      }
//      cerr << "       " << k << " " << tmp << " " << kq[k] << " " << le[k] << " " << ri[k] << " t\n";
    }
    int ptr = 0, lag = (int)rrh.size();

    for(int k = 1; k <= q; k ++){
      while(ptr < lag && pt[ptr + 1] < A[k]) ptr++;
      if(!ptr){
        int i = ptr + 1;
        cout << kq[i] + 1ll * ri[i] * (pt[i] - A[k]) << "\n";
        continue;
      }
      if(ptr == lag){
        int i = ptr;
        cout << kq[ptr] + 1ll * le[i] * (A[k] - pt[ptr]) << "\n";
        continue;
      }
      ll B = kq[ptr] + 1ll * le[ptr] * (A[k] - pt[ptr]) - 1ll * (n - 1 - le[ptr]) * (A[k] - pt[ptr]);
      ll C = kq[ptr + 1] + 1ll * ri[ptr + 1] * (pt[ptr + 1] - A[k]) - 1ll * (n - 1 - ri[ptr + 1]) * (pt[ptr + 1] - A[k]);
//      cerr << B << " " << C << " r\n";
      cout << min(B, C) << "\n";
    }
  }
}
/*
4 6
1 2 2
2 3 16
3 4 3
3 4 3
2 4 13
1 3 7
5
5 7 8 8 10
*/

namespace sub3{
  vector<int> vr[N];
  ll st[N << 2], lz[N << 2], T[N << 2];

  void dolz(int i){
    if(!lz[i]) return;
    int x = lz[i]; lz[i] = 0;
    lz[i << 1] += x;
    lz[i << 1|1] += x;
    st[i << 1] += x;
    st[i << 1|1] += x;
    T[i << 1] += T[i];
    T[i << 1|1] += T[i];
    T[i] = 0;
  }

  void update(int i,int l,int r,int u,int v,int val,int type){
    if(l > r || r < u || v < l) return;
    if(u <= l && r <= v){
      st[i] += val;
      T[i] += type;
      lz[i] += val;
      return;
    }
    dolz(i);
    int mid = (l + r) / 2;
    update(i << 1, l, mid, u, v, val, type);
    update(i << 1|1, mid + 1, r, u, v, val, type);
  }

  int idx[N];

  int get(int i,int l,int r,int u){
    if(l > r || r < u || u < l) return 0;
    if(l == r){
      idx[u] = i;
      return st[i];
    }
    dolz(i);
    int mid = (l + r) / 2;
    return get(i << 1, l, mid, u) + get(i << 1|1, mid + 1, r, u);
  }

  void solve(){
    sort(A + 1, A + q + 1);
    for(int i = 1; i <= m; i ++){
      vr[_x[i]].push_back(_c[i]);
    }
    for(int i = 1; i < n; i ++){
      sort(all(vr[i]));
      for(int j = 0; j < vr[i].size(); j ++){
        if(!j){
          int pos = upper_bound(A + 1, A + q + 1, vr[i][j] - 1) - A - 1;
          if(pos >= 1){
            update(1, 1, q, 1, pos, vr[i][j], 0);
          }
          continue;
        }
        int pre = vr[i][j - 1];
        int x = vr[i][j];
        int mid = (x + pre) / 2;
        int _right = upper_bound(A + 1, A + q + 1, mid) - A - 1;
        int _left = lower_bound(A + 1, A + q + 1, pre) - A;
        if(_left <= _right) update(1, 1, q, _left, _right, -pre, 1);
        _right = upper_bound(A + 1, A + q + 1, x) - A - 1;
        _left = lower_bound(A + 1, A + q + 1, mid + 1) - A;
        if(_left <= _right) update(1, 1, q, _left, _right, x, 0);
      }
      int pos = lower_bound(A + 1, A + q + 1, vr[i].back() + ((int)vr[i].size() > 1)) - A;
      if(pos <= q){
        update(1, 1, q, pos, q, -vr[i].back(), 1);
      }
    }
    for(int i = 1; i <= q; i ++){
      int val = get(1, 1, q, i);
      int pos = idx[i];
      cout << val + T[pos] * A[i] - (n - 1 - T[pos]) * A[i] << "\n";
    }
  }

}

namespace sub2{
  int pa[N], sz[N];
  int fin(int u){
    return pa[u] == u ? u : pa[u] = fin(pa[u]);
  }

  bool dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return 0;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    pa[v] = u;
    return 1;
  }

  void solve(){
    for(int k = 1; k <= q; k ++){
      vector<tuple<int,int,int>> edge;
      ll ans = 0;
      for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
      for(int i = 1; i <= m; i ++){
         edge.push_back({abs(_c[i] - A[k]), _x[i], _y[i]});
      }
      sort(all(edge));
      for(auto [val, x, y] : edge){
        if(dsu(x, y)) ans += val;
      }
      cout << ans << "\n";
    }
  }
}

namespace sub1{
  #define int long long
  bool flag[N];
  vector<int> p[N];
  void solve(){
    for(int k = 1; k <= q; k ++){
      int ans = 1e18;
      for(int msk = 0; msk < (1 << m); msk ++){
        for(int i = 1; i <= n; i ++){
          flag[i] = 0;
          p[i].clear();
        }
        int cnt = 0;
        for(int i = 1; i <= m; i ++) if(msk >> (i - 1) & 1){
          int x = _x[i];
          int y = _y[i];
          p[x].push_back(y);
          p[y].push_back(x);
          cnt += abs(_c[i] - A[k]);
        }
        queue<int> q;
        q.push(1);
        flag[1] = 1;
        while(!q.empty()){
          int u = q.front(); q.pop();
          for(auto j : p[u]) if(!flag[j]){
            q.push(j);
            flag[j] = 1;
          }
        }
        bool ff = true;
        for(int i = 1; i <= n; i ++) if(!flag[i]){
          ff = false;
          break;
        }
        if(ff) ans = min(ans, cnt);
      }
      cout << ans << "\n";
    }

  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "repj"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  bool ff = true;
  for(int i = 1; i <= m; i ++){
    cin >> _x[i] >> _y[i] >> _c[i];
    if(_y[i] != _x[i] + 1) ff = false;
  }
  cin >> q;
  for(int i = 1; i <= q; i ++) cin >> A[i];

  if(m <= 16 && q <= 10) sub1 :: solve();
  else if(q <= 10) sub2 :: solve();
  else if(ff) sub3 :: solve();
  else sub4 :: solve();
}

Compilation message

reconstruction.cpp: In function 'void sub4::solve()':
reconstruction.cpp:40:10: warning: unused variable 'ans' [-Wunused-variable]
   40 |       ll ans = 0;
      |          ^~~
reconstruction.cpp: In function 'void sub3::solve()':
reconstruction.cpp:139:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |       for(int j = 0; j < vr[i].size(); j ++){
      |                      ~~^~~~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:251:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:252:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57936 KB Output is correct
2 Correct 10 ms 57936 KB Output is correct
3 Correct 91 ms 57936 KB Output is correct
4 Correct 93 ms 57936 KB Output is correct
5 Correct 98 ms 57948 KB Output is correct
6 Correct 112 ms 57948 KB Output is correct
7 Correct 115 ms 57936 KB Output is correct
8 Correct 110 ms 58076 KB Output is correct
9 Correct 104 ms 58104 KB Output is correct
10 Correct 112 ms 57936 KB Output is correct
11 Correct 120 ms 57936 KB Output is correct
12 Correct 9 ms 57936 KB Output is correct
13 Correct 81 ms 57936 KB Output is correct
14 Correct 93 ms 57936 KB Output is correct
15 Correct 89 ms 57936 KB Output is correct
16 Correct 114 ms 57936 KB Output is correct
17 Correct 124 ms 58076 KB Output is correct
18 Correct 120 ms 57936 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57936 KB Output is correct
2 Correct 10 ms 57936 KB Output is correct
3 Correct 91 ms 57936 KB Output is correct
4 Correct 93 ms 57936 KB Output is correct
5 Correct 98 ms 57948 KB Output is correct
6 Correct 112 ms 57948 KB Output is correct
7 Correct 115 ms 57936 KB Output is correct
8 Correct 110 ms 58076 KB Output is correct
9 Correct 104 ms 58104 KB Output is correct
10 Correct 112 ms 57936 KB Output is correct
11 Correct 120 ms 57936 KB Output is correct
12 Correct 9 ms 57936 KB Output is correct
13 Correct 81 ms 57936 KB Output is correct
14 Correct 93 ms 57936 KB Output is correct
15 Correct 89 ms 57936 KB Output is correct
16 Correct 114 ms 57936 KB Output is correct
17 Correct 124 ms 58076 KB Output is correct
18 Correct 120 ms 57936 KB Output is correct
19 Correct 9 ms 59984 KB Output is correct
20 Correct 113 ms 66960 KB Output is correct
21 Correct 114 ms 66964 KB Output is correct
22 Correct 114 ms 66984 KB Output is correct
23 Correct 114 ms 66960 KB Output is correct
24 Correct 114 ms 66956 KB Output is correct
25 Correct 109 ms 66960 KB Output is correct
26 Correct 114 ms 66960 KB Output is correct
27 Correct 115 ms 66980 KB Output is correct
28 Correct 139 ms 66952 KB Output is correct
29 Correct 153 ms 66976 KB Output is correct
30 Correct 119 ms 66976 KB Output is correct
31 Correct 112 ms 66964 KB Output is correct
32 Correct 123 ms 66952 KB Output is correct
33 Correct 116 ms 66948 KB Output is correct
34 Correct 141 ms 66980 KB Output is correct
35 Correct 114 ms 66976 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 57936 KB Output is correct
2 Correct 12 ms 57936 KB Output is correct
3 Correct 86 ms 57936 KB Output is correct
4 Incorrect 473 ms 136208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57936 KB Output is correct
2 Correct 10 ms 57936 KB Output is correct
3 Correct 91 ms 57936 KB Output is correct
4 Correct 93 ms 57936 KB Output is correct
5 Correct 98 ms 57948 KB Output is correct
6 Correct 112 ms 57948 KB Output is correct
7 Correct 115 ms 57936 KB Output is correct
8 Correct 110 ms 58076 KB Output is correct
9 Correct 104 ms 58104 KB Output is correct
10 Correct 112 ms 57936 KB Output is correct
11 Correct 120 ms 57936 KB Output is correct
12 Correct 9 ms 57936 KB Output is correct
13 Correct 81 ms 57936 KB Output is correct
14 Correct 93 ms 57936 KB Output is correct
15 Correct 89 ms 57936 KB Output is correct
16 Correct 114 ms 57936 KB Output is correct
17 Correct 124 ms 58076 KB Output is correct
18 Correct 120 ms 57936 KB Output is correct
19 Correct 10 ms 59984 KB Output is correct
20 Incorrect 196 ms 84200 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57936 KB Output is correct
2 Correct 10 ms 57936 KB Output is correct
3 Correct 91 ms 57936 KB Output is correct
4 Correct 93 ms 57936 KB Output is correct
5 Correct 98 ms 57948 KB Output is correct
6 Correct 112 ms 57948 KB Output is correct
7 Correct 115 ms 57936 KB Output is correct
8 Correct 110 ms 58076 KB Output is correct
9 Correct 104 ms 58104 KB Output is correct
10 Correct 112 ms 57936 KB Output is correct
11 Correct 120 ms 57936 KB Output is correct
12 Correct 9 ms 57936 KB Output is correct
13 Correct 81 ms 57936 KB Output is correct
14 Correct 93 ms 57936 KB Output is correct
15 Correct 89 ms 57936 KB Output is correct
16 Correct 114 ms 57936 KB Output is correct
17 Correct 124 ms 58076 KB Output is correct
18 Correct 120 ms 57936 KB Output is correct
19 Correct 9 ms 59984 KB Output is correct
20 Correct 113 ms 66960 KB Output is correct
21 Correct 114 ms 66964 KB Output is correct
22 Correct 114 ms 66984 KB Output is correct
23 Correct 114 ms 66960 KB Output is correct
24 Correct 114 ms 66956 KB Output is correct
25 Correct 109 ms 66960 KB Output is correct
26 Correct 114 ms 66960 KB Output is correct
27 Correct 115 ms 66980 KB Output is correct
28 Correct 139 ms 66952 KB Output is correct
29 Correct 153 ms 66976 KB Output is correct
30 Correct 119 ms 66976 KB Output is correct
31 Correct 112 ms 66964 KB Output is correct
32 Correct 123 ms 66952 KB Output is correct
33 Correct 116 ms 66948 KB Output is correct
34 Correct 141 ms 66980 KB Output is correct
35 Correct 114 ms 66976 KB Output is correct
36 Execution timed out 5034 ms 74672 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57936 KB Output is correct
2 Correct 10 ms 57936 KB Output is correct
3 Correct 91 ms 57936 KB Output is correct
4 Correct 93 ms 57936 KB Output is correct
5 Correct 98 ms 57948 KB Output is correct
6 Correct 112 ms 57948 KB Output is correct
7 Correct 115 ms 57936 KB Output is correct
8 Correct 110 ms 58076 KB Output is correct
9 Correct 104 ms 58104 KB Output is correct
10 Correct 112 ms 57936 KB Output is correct
11 Correct 120 ms 57936 KB Output is correct
12 Correct 9 ms 57936 KB Output is correct
13 Correct 81 ms 57936 KB Output is correct
14 Correct 93 ms 57936 KB Output is correct
15 Correct 89 ms 57936 KB Output is correct
16 Correct 114 ms 57936 KB Output is correct
17 Correct 124 ms 58076 KB Output is correct
18 Correct 120 ms 57936 KB Output is correct
19 Correct 9 ms 59984 KB Output is correct
20 Correct 113 ms 66960 KB Output is correct
21 Correct 114 ms 66964 KB Output is correct
22 Correct 114 ms 66984 KB Output is correct
23 Correct 114 ms 66960 KB Output is correct
24 Correct 114 ms 66956 KB Output is correct
25 Correct 109 ms 66960 KB Output is correct
26 Correct 114 ms 66960 KB Output is correct
27 Correct 115 ms 66980 KB Output is correct
28 Correct 139 ms 66952 KB Output is correct
29 Correct 153 ms 66976 KB Output is correct
30 Correct 119 ms 66976 KB Output is correct
31 Correct 112 ms 66964 KB Output is correct
32 Correct 123 ms 66952 KB Output is correct
33 Correct 116 ms 66948 KB Output is correct
34 Correct 141 ms 66980 KB Output is correct
35 Correct 114 ms 66976 KB Output is correct
36 Correct 13 ms 57936 KB Output is correct
37 Correct 12 ms 57936 KB Output is correct
38 Correct 86 ms 57936 KB Output is correct
39 Incorrect 473 ms 136208 KB Output isn't correct
40 Halted 0 ms 0 KB -