oj.uz

Submission #1119232

# Submission time Handle Problem Language Result Execution time Memory
1119232 2024-11-26T17:23:45 Z VinhLuu Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 2270 ms 78636 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<ll, ll> pii;

const int N = 1e5 + 5;
const int M = 1e6 + 5;

struct _edge{
  int a, b, c;
} h[N];

int n, m, q, W[M];

int nxt[N], wt[N], sz[N], pa[N], cnt, demin, in[N], en[N];
bool flag[N];
vector<int> edge;
vector<pair<int,int>> p[N];

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

void dsu(int x,int y){
  x = fin(x);
  y = fin(y);
  if(x == y) return;
  if(sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  pa[y] = x;
}

void dfs(int u,int v){
  in[u] = ++demin;
//  cerr << u << " " << v << " s\n";
  for(auto [j, w] : p[u]) if(j != v) {
    nxt[j] = u;
    wt[j] = w;
    dfs(j, u);
  }
  en[u] = ++demin;
}

bool kt(int u, int v){
  return in[u] <= in[v] && in[v] <= en[u];
}

void reset(){
  for(int i = 1; i <= n; i ++){
    in[i] = en[i] = wt[i] = nxt[i] = 0, pa[i] = i, sz[i] = 1;
    p[i].clear();
  }
  demin = 0;
}

vector<tuple<int,int,int>> imp;
vector<int> rrh, weight, Q[N];
vector<pair<int,int>> change[N];
int kq[M];

ll bit[N], T[N];
int sze;

void add(int i,int val,int x){
  for(; i <= sze; i += i & -i) bit[i] += val, T[i] += x;
}

pair<ll,ll> get(int i){
  int cnt = 0, ret = 0;
  for(;i > 0; i -= i & -i){
    cnt += bit[i];
    ret += T[i];
  }
  return {cnt, ret};
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  for(int i = 1; i <= m; i ++){
    cin >> h[i].a >> h[i].b >> h[i].c;
    weight.push_back(h[i].c);
  }

  sort(all(weight)); weight.resize(unique(all(weight)) - weight.begin());
  sze = (int)weight.size();

  cin >> q;
  for(int i = 1; i <= q; i ++) cin >> W[i];

  sort(h + 1, h + m + 1, [&](_edge x, _edge y){return x.c < y.c;});

//  for(int i = 1; i <= m; i ++) cerr << h[i].a << " " << h[i].b << " " << h[i].c << " \n";

  reset();
  bool ff = true;

  /*
  4 5 2
  1 5 3
  1 4 5
  3 4 6
  3 5 6
  2 3 7
  1 2 8
  1 5 11
  1 3 13
  2 4 15
  */


  for(int i = 1; i <= m; i ++){
    int x = h[i].a, y = h[i].b, w = h[i].c;
//    cerr << i << " " << " " << x << " " << y << " " << w << " h\n";
    if(ff == false || fin(x) == fin(y)){
      reset();
      vector<int> new_edge;
      for(auto j : edge) if(flag[j]) {
//        cerr << h[j].a << " " << h[j].b << " e\n";
        p[h[j].a].push_back({h[j].b, j});
        p[h[j].b].push_back({h[j].a, j});
      }
      for(int i = 1; i <= n; i ++) if(!in[i]) dfs(i, 0);
      int mi = m + 1, px = x, py = y;
      while(!kt(px, y)){
        mi = min(mi, wt[px]);
        px = nxt[px];
      }
      while(!kt(py, x)){
        mi = min(mi, wt[py]);
        py = nxt[py];
      }
      int mid = (w + h[mi].c) / 2 + 1;
      imp.push_back({mid, h[mi].c, w});
      rrh.push_back(mid);
      flag[mi] = 0;
      flag[i] = 1;
      for(auto j : edge) if(flag[j]) {
        new_edge.push_back(j);
        dsu(h[j].a, h[j].b);
      }
      swap(new_edge, edge);
      edge.push_back(i);
      dsu(h[i].a, h[i].b);
    }else{
      dsu(x, y);
      flag[i] = 1;
      edge.push_back(i);
      cnt++;
      if(cnt == n - 1) ff = false;
    }
  }


  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
  for(auto [w, x, y] : imp) {
    int pos = lower_bound(all(rrh), w) - rrh.begin() + 1;
    change[pos].push_back({x, y});
  }
  for(int i = 1; i <= q; i ++){
    int pos = upper_bound(all(rrh), W[i]) - rrh.begin();
    Q[pos].push_back(i);
  }
  reset();
  for(int i = 1; i <= m; i ++) {
    int x = h[i].a, y = h[i].b, w = h[i].c;

    int valx = fin(x);
    int valy = fin(y);
    if(valx != valy){

      dsu(x, y);
      int pw = lower_bound(all(weight), w) - weight.begin() + 1;
      add(pw, 1, w);
    }
  }

  for(int k = 0; k <= (int)rrh.size(); k ++) {
    for(auto [x, y] : change[k]) {
      int px = lower_bound(all(weight), x) - weight.begin() + 1;
      int py = lower_bound(all(weight), y) - weight.begin() + 1;
      add(px, -1, -x);
      add(py, 1, y);
    }
    for(auto i : Q[k]) {
      int pos = upper_bound(all(weight), W[i]) - weight.begin();
      auto le = get(pos);
      auto ri = get(sze);
      ri = {ri.first - le.first, ri.second - le.second};
      kq[i] = 1ll * le.first * W[i] - le.second + ri.second - 1ll * ri.first * W[i];
    }
  }

  for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct
2 Correct 4 ms 18768 KB Output is correct
3 Correct 4 ms 18768 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Correct 4 ms 18768 KB Output is correct
6 Correct 5 ms 18768 KB Output is correct
7 Correct 3 ms 18768 KB Output is correct
8 Correct 4 ms 18768 KB Output is correct
9 Correct 3 ms 18920 KB Output is correct
10 Correct 4 ms 18768 KB Output is correct
11 Correct 4 ms 18944 KB Output is correct
12 Correct 4 ms 18768 KB Output is correct
13 Correct 5 ms 18768 KB Output is correct
14 Correct 3 ms 18768 KB Output is correct
15 Correct 3 ms 18768 KB Output is correct
16 Correct 4 ms 18768 KB Output is correct
17 Correct 4 ms 18768 KB Output is correct
18 Correct 5 ms 18768 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 1721 ms 26460 KB Output is correct
21 Correct 1535 ms 26544 KB Output is correct
22 Correct 1746 ms 26644 KB Output is correct
23 Correct 1773 ms 26580 KB Output is correct
24 Correct 1813 ms 26476 KB Output is correct
25 Correct 1811 ms 26564 KB Output is correct
26 Correct 1794 ms 26432 KB Output is correct
27 Correct 1948 ms 26420 KB Output is correct
28 Correct 1943 ms 25444 KB Output is correct
29 Correct 1817 ms 25464 KB Output is correct
30 Correct 1817 ms 26608 KB Output is correct
31 Correct 1711 ms 26452 KB Output is correct
32 Correct 1676 ms 26440 KB Output is correct
33 Correct 1737 ms 26608 KB Output is correct
34 Correct 1797 ms 27748 KB Output is correct
35 Correct 1816 ms 26424 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18768 KB Output is correct
2 Correct 3 ms 18768 KB Output is correct
3 Correct 4 ms 18768 KB Output is correct
4 Correct 2161 ms 62060 KB Output is correct
5 Correct 2164 ms 73508 KB Output is correct
6 Correct 2270 ms 73580 KB Output is correct
7 Correct 1334 ms 75440 KB Output is correct
8 Correct 1293 ms 75552 KB Output is correct
9 Correct 1329 ms 75544 KB Output is correct
10 Correct 1995 ms 70524 KB Output is correct
11 Correct 1309 ms 78636 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct
2 Correct 4 ms 18768 KB Output is correct
3 Correct 4 ms 18768 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Correct 4 ms 18768 KB Output is correct
6 Correct 5 ms 18768 KB Output is correct
7 Correct 3 ms 18768 KB Output is correct
8 Correct 4 ms 18768 KB Output is correct
9 Correct 3 ms 18920 KB Output is correct
10 Correct 4 ms 18768 KB Output is correct
11 Correct 4 ms 18944 KB Output is correct
12 Correct 4 ms 18768 KB Output is correct
13 Correct 5 ms 18768 KB Output is correct
14 Correct 3 ms 18768 KB Output is correct
15 Correct 3 ms 18768 KB Output is correct
16 Correct 4 ms 18768 KB Output is correct
17 Correct 4 ms 18768 KB Output is correct
18 Correct 5 ms 18768 KB Output is correct
19 Correct 4 ms 18768 KB Output is correct
20 Correct 269 ms 52304 KB Output is correct
21 Correct 241 ms 59332 KB Output is correct
22 Correct 232 ms 57304 KB Output is correct
23 Correct 246 ms 55988 KB Output is correct
24 Correct 214 ms 56920 KB Output is correct
25 Correct 303 ms 56536 KB Output is correct
26 Correct 265 ms 55532 KB Output is correct
27 Correct 254 ms 54136 KB Output is correct
28 Correct 293 ms 54920 KB Output is correct
29 Correct 246 ms 55740 KB Output is correct
30 Correct 244 ms 61732 KB Output is correct
31 Correct 239 ms 56676 KB Output is correct
32 Correct 255 ms 56352 KB Output is correct
33 Correct 263 ms 54428 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct
2 Correct 4 ms 18768 KB Output is correct
3 Correct 4 ms 18768 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Correct 4 ms 18768 KB Output is correct
6 Correct 5 ms 18768 KB Output is correct
7 Correct 3 ms 18768 KB Output is correct
8 Correct 4 ms 18768 KB Output is correct
9 Correct 3 ms 18920 KB Output is correct
10 Correct 4 ms 18768 KB Output is correct
11 Correct 4 ms 18944 KB Output is correct
12 Correct 4 ms 18768 KB Output is correct
13 Correct 5 ms 18768 KB Output is correct
14 Correct 3 ms 18768 KB Output is correct
15 Correct 3 ms 18768 KB Output is correct
16 Correct 4 ms 18768 KB Output is correct
17 Correct 4 ms 18768 KB Output is correct
18 Correct 5 ms 18768 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 1721 ms 26460 KB Output is correct
21 Correct 1535 ms 26544 KB Output is correct
22 Correct 1746 ms 26644 KB Output is correct
23 Correct 1773 ms 26580 KB Output is correct
24 Correct 1813 ms 26476 KB Output is correct
25 Correct 1811 ms 26564 KB Output is correct
26 Correct 1794 ms 26432 KB Output is correct
27 Correct 1948 ms 26420 KB Output is correct
28 Correct 1943 ms 25444 KB Output is correct
29 Correct 1817 ms 25464 KB Output is correct
30 Correct 1817 ms 26608 KB Output is correct
31 Correct 1711 ms 26452 KB Output is correct
32 Correct 1676 ms 26440 KB Output is correct
33 Correct 1737 ms 26608 KB Output is correct
34 Correct 1797 ms 27748 KB Output is correct
35 Correct 1816 ms 26424 KB Output is correct
36 Correct 1796 ms 20052 KB Output is correct
37 Correct 1608 ms 22112 KB Output is correct
38 Correct 1734 ms 22208 KB Output is correct
39 Correct 1903 ms 22820 KB Output is correct
40 Correct 1797 ms 22204 KB Output is correct
41 Correct 1636 ms 29116 KB Output is correct
42 Correct 1783 ms 22740 KB Output is correct
43 Correct 1862 ms 21372 KB Output is correct
44 Correct 1823 ms 18724 KB Output is correct
45 Correct 1787 ms 18680 KB Output is correct
46 Correct 1856 ms 22060 KB Output is correct
47 Correct 1654 ms 23352 KB Output is correct
48 Correct 1667 ms 21536 KB Output is correct
49 Correct 1839 ms 21564 KB Output is correct
50 Correct 1849 ms 20600 KB Output is correct
51 Correct 1865 ms 21216 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct
2 Correct 4 ms 18768 KB Output is correct
3 Correct 4 ms 18768 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Correct 4 ms 18768 KB Output is correct
6 Correct 5 ms 18768 KB Output is correct
7 Correct 3 ms 18768 KB Output is correct
8 Correct 4 ms 18768 KB Output is correct
9 Correct 3 ms 18920 KB Output is correct
10 Correct 4 ms 18768 KB Output is correct
11 Correct 4 ms 18944 KB Output is correct
12 Correct 4 ms 18768 KB Output is correct
13 Correct 5 ms 18768 KB Output is correct
14 Correct 3 ms 18768 KB Output is correct
15 Correct 3 ms 18768 KB Output is correct
16 Correct 4 ms 18768 KB Output is correct
17 Correct 4 ms 18768 KB Output is correct
18 Correct 5 ms 18768 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 1721 ms 26460 KB Output is correct
21 Correct 1535 ms 26544 KB Output is correct
22 Correct 1746 ms 26644 KB Output is correct
23 Correct 1773 ms 26580 KB Output is correct
24 Correct 1813 ms 26476 KB Output is correct
25 Correct 1811 ms 26564 KB Output is correct
26 Correct 1794 ms 26432 KB Output is correct
27 Correct 1948 ms 26420 KB Output is correct
28 Correct 1943 ms 25444 KB Output is correct
29 Correct 1817 ms 25464 KB Output is correct
30 Correct 1817 ms 26608 KB Output is correct
31 Correct 1711 ms 26452 KB Output is correct
32 Correct 1676 ms 26440 KB Output is correct
33 Correct 1737 ms 26608 KB Output is correct
34 Correct 1797 ms 27748 KB Output is correct
35 Correct 1816 ms 26424 KB Output is correct
36 Correct 4 ms 18768 KB Output is correct
37 Correct 3 ms 18768 KB Output is correct
38 Correct 4 ms 18768 KB Output is correct
39 Correct 2161 ms 62060 KB Output is correct
40 Correct 2164 ms 73508 KB Output is correct
41 Correct 2270 ms 73580 KB Output is correct
42 Correct 1334 ms 75440 KB Output is correct
43 Correct 1293 ms 75552 KB Output is correct
44 Correct 1329 ms 75544 KB Output is correct
45 Correct 1995 ms 70524 KB Output is correct
46 Correct 1309 ms 78636 KB Output is correct
47 Correct 4 ms 18768 KB Output is correct
48 Correct 269 ms 52304 KB Output is correct
49 Correct 241 ms 59332 KB Output is correct
50 Correct 232 ms 57304 KB Output is correct
51 Correct 246 ms 55988 KB Output is correct
52 Correct 214 ms 56920 KB Output is correct
53 Correct 303 ms 56536 KB Output is correct
54 Correct 265 ms 55532 KB Output is correct
55 Correct 254 ms 54136 KB Output is correct
56 Correct 293 ms 54920 KB Output is correct
57 Correct 246 ms 55740 KB Output is correct
58 Correct 244 ms 61732 KB Output is correct
59 Correct 239 ms 56676 KB Output is correct
60 Correct 255 ms 56352 KB Output is correct
61 Correct 263 ms 54428 KB Output is correct
62 Correct 1796 ms 20052 KB Output is correct
63 Correct 1608 ms 22112 KB Output is correct
64 Correct 1734 ms 22208 KB Output is correct
65 Correct 1903 ms 22820 KB Output is correct
66 Correct 1797 ms 22204 KB Output is correct
67 Correct 1636 ms 29116 KB Output is correct
68 Correct 1783 ms 22740 KB Output is correct
69 Correct 1862 ms 21372 KB Output is correct
70 Correct 1823 ms 18724 KB Output is correct
71 Correct 1787 ms 18680 KB Output is correct
72 Correct 1856 ms 22060 KB Output is correct
73 Correct 1654 ms 23352 KB Output is correct
74 Correct 1667 ms 21536 KB Output is correct
75 Correct 1839 ms 21564 KB Output is correct
76 Correct 1849 ms 20600 KB Output is correct
77 Correct 1865 ms 21216 KB Output is correct
78 Correct 2113 ms 67956 KB Output is correct
79 Correct 1974 ms 72024 KB Output is correct
80 Correct 1983 ms 69020 KB Output is correct
81 Correct 2005 ms 68824 KB Output is correct
82 Correct 2136 ms 68000 KB Output is correct
83 Correct 2060 ms 67924 KB Output is correct
84 Correct 2132 ms 67996 KB Output is correct
85 Correct 2131 ms 67928 KB Output is correct
86 Correct 2019 ms 63580 KB Output is correct
87 Correct 1843 ms 63552 KB Output is correct
88 Correct 2116 ms 67832 KB Output is correct
89 Correct 2210 ms 67968 KB Output is correct
90 Correct 2062 ms 67500 KB Output is correct
91 Correct 2182 ms 67436 KB Output is correct
92 Correct 2013 ms 65744 KB Output is correct
93 Correct 1870 ms 66072 KB Output is correct