oj.uz

Submission #1087686

# Submission time Handle Problem Language Result Execution time Memory
1087686 2024-09-13T05:48:55 Z vladilius Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 426848 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const int inf = 1e9 + 5;
const int N = 5e2;

struct dsu{
    int sz[N + 1], p[N + 1], n;
    vector<int> ed;
    ll W;
    dsu(int ns){
        n = ns;
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y, int w){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
        W += w;
        ed.pb(w);
    }
    void clear(){
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
        ed.clear();
        W = 0;
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<arr3> ed = {{0, 0, 0}};
    for (int i = 1; i <= m; i++){
        int a, b, w; cin>>a>>b>>w;
        ed.pb({a, b, w});
    }
    ed.pb({0, 0, inf});
 
    auto cmp = [&](arr3& x, arr3& y){
        return x[2] < y[2];
    };
    sort(ed.begin(), ed.end(), cmp);
    
    vector<int> actl[m + 2];
    dsu T(n);
    for (int i = 1; i <= m; i++){
        T.clear();
        T.unite(ed[i][0], ed[i][1], i);
        for (int j: actl[i - 1]){
            T.unite(ed[j][0], ed[j][1], j);
        }
        actl[i] = T.ed;
    }
    
    vector<int> actr[m + 2];
    for (int i = m; i > 0; i--){
        T.clear();
        T.unite(ed[i][0], ed[i][1], i);
        for (int j: actr[i + 1]){
            T.unite(ed[j][0], ed[j][1], j);
        }
        actr[i] = T.ed;
    }
    
    int q; cin>>q;
    vector<pii> qs;
    for (int i = 1; i <= q; i++){
        int x; cin>>x;
        qs.pb({x, i});
    }
    sort(qs.begin(), qs.end());
 
    vector<ll> out(q + 1);
    int j1 = 0;
    for (int i = 0; i <= m; i++){
        vector<int>& edg1 = actl[i], edg2 = actr[i + 1];
        
        int l = ed[i][2], r = ed[i + 1][2] - 1;
        int j2 = j1;
        while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
            j2++;
        }
        while (j1 < j2){
            int x = qs[j1].ff;
            int i1 = 0, i2 = 0;
            T.clear();
            while (i1 < edg1.size() || i2 < edg2.size()){
                if (i1 == edg1.size()){
                    int j = edg2[i2];
                    T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x));
                    i2++;
                    continue;
                }
                if (i2 == edg2.size()){
                    int j = edg1[i1];
                    T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x));
                    i1++;
                    continue;
                }
                int v1 = abs(ed[edg1[i1]][2] - x);
                int v2 = abs(ed[edg2[i2]][2] - x);
                if (v1 < v2){
                    int j = edg1[i1];
                    T.unite(ed[j][0], ed[j][1], v1);
                    i1++;
                }
                else {
                    int j = edg2[i2];
                    T.unite(ed[j][0], ed[j][1], v2);
                    i2++;
                }
            }
            out[qs[j1].ss] = T.W;
            j1++;
        }
    }
    
    for (int i = 1; i <= q; i++) cout<<out[i]<<"\n";
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
      |                ~~~^~~~~~~~~~~
reconstruction.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                    ~~~^~~~~~~~~~~~~
reconstruction.cpp:106:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                                        ~~~^~~~~~~~~~~~~
reconstruction.cpp:107:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |                 if (i1 == edg1.size()){
      |                     ~~~^~~~~~~~~~~~~~
reconstruction.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 if (i2 == edg2.size()){
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1080 ms 401380 KB Output is correct
21 Correct 973 ms 379588 KB Output is correct
22 Correct 1022 ms 396172 KB Output is correct
23 Correct 1204 ms 400324 KB Output is correct
24 Correct 1078 ms 400836 KB Output is correct
25 Correct 1128 ms 401096 KB Output is correct
26 Correct 1094 ms 401348 KB Output is correct
27 Correct 1149 ms 401352 KB Output is correct
28 Correct 1208 ms 401424 KB Output is correct
29 Correct 1071 ms 401252 KB Output is correct
30 Correct 1042 ms 401116 KB Output is correct
31 Correct 1092 ms 401340 KB Output is correct
32 Correct 1053 ms 401256 KB Output is correct
33 Correct 1093 ms 401232 KB Output is correct
34 Correct 1034 ms 401444 KB Output is correct
35 Correct 1233 ms 401160 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 5103 ms 426848 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 460 KB Output is correct
20 Execution timed out 5088 ms 28656 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1080 ms 401380 KB Output is correct
21 Correct 973 ms 379588 KB Output is correct
22 Correct 1022 ms 396172 KB Output is correct
23 Correct 1204 ms 400324 KB Output is correct
24 Correct 1078 ms 400836 KB Output is correct
25 Correct 1128 ms 401096 KB Output is correct
26 Correct 1094 ms 401348 KB Output is correct
27 Correct 1149 ms 401352 KB Output is correct
28 Correct 1208 ms 401424 KB Output is correct
29 Correct 1071 ms 401252 KB Output is correct
30 Correct 1042 ms 401116 KB Output is correct
31 Correct 1092 ms 401340 KB Output is correct
32 Correct 1053 ms 401256 KB Output is correct
33 Correct 1093 ms 401232 KB Output is correct
34 Correct 1034 ms 401444 KB Output is correct
35 Correct 1233 ms 401160 KB Output is correct
36 Correct 1560 ms 402116 KB Output is correct
37 Correct 1407 ms 380464 KB Output is correct
38 Correct 1485 ms 396996 KB Output is correct
39 Correct 1448 ms 401008 KB Output is correct
40 Correct 1638 ms 401636 KB Output is correct
41 Correct 1481 ms 401848 KB Output is correct
42 Correct 1480 ms 401912 KB Output is correct
43 Correct 1531 ms 402116 KB Output is correct
44 Correct 1261 ms 402076 KB Output is correct
45 Correct 1180 ms 402112 KB Output is correct
46 Correct 1505 ms 402052 KB Output is correct
47 Correct 1501 ms 402188 KB Output is correct
48 Correct 1469 ms 401988 KB Output is correct
49 Correct 1473 ms 402172 KB Output is correct
50 Correct 1150 ms 402132 KB Output is correct
51 Correct 1211 ms 401936 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1080 ms 401380 KB Output is correct
21 Correct 973 ms 379588 KB Output is correct
22 Correct 1022 ms 396172 KB Output is correct
23 Correct 1204 ms 400324 KB Output is correct
24 Correct 1078 ms 400836 KB Output is correct
25 Correct 1128 ms 401096 KB Output is correct
26 Correct 1094 ms 401348 KB Output is correct
27 Correct 1149 ms 401352 KB Output is correct
28 Correct 1208 ms 401424 KB Output is correct
29 Correct 1071 ms 401252 KB Output is correct
30 Correct 1042 ms 401116 KB Output is correct
31 Correct 1092 ms 401340 KB Output is correct
32 Correct 1053 ms 401256 KB Output is correct
33 Correct 1093 ms 401232 KB Output is correct
34 Correct 1034 ms 401444 KB Output is correct
35 Correct 1233 ms 401160 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Execution timed out 5103 ms 426848 KB Time limit exceeded
40 Halted 0 ms 0 KB -