oj.uz

Submission #1087688

# Submission time Handle Problem Language Result Execution time Memory
1087688 2024-09-13T05:53:28 Z vladilius Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 426700 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 dsu1{
    int sz[N + 1], p[N + 1], n;
    vector<int> ed;
    ll W;
    dsu1(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;
    }
};

struct dsu{
    int sz[N + 1], p[N + 1], n;
    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;
    }
    void clear(){
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
        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];
    dsu1 T1(n);
    for (int i = 1; i <= m; i++){
        T1.clear();
        T1.unite(ed[i][0], ed[i][1], i);
        for (int j: actl[i - 1]){
            T1.unite(ed[j][0], ed[j][1], j);
        }
        actl[i] = T1.ed;
    }
    
    vector<int> actr[m + 2];
    for (int i = m; i > 0; i--){
        T1.clear();
        T1.unite(ed[i][0], ed[i][1], i);
        for (int j: actr[i + 1]){
            T1.unite(ed[j][0], ed[j][1], j);
        }
        actr[i] = T1.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;
    dsu T(n);
    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:129: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]
  129 |         while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
      |                ~~~^~~~~~~~~~~
reconstruction.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                    ~~~^~~~~~~~~~~~~
reconstruction.cpp:136:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                                        ~~~^~~~~~~~~~~~~
reconstruction.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                 if (i1 == edg1.size()){
      |                     ~~~^~~~~~~~~~~~~~
reconstruction.cpp:143:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 if (i2 == edg2.size()){
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 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 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 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 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1027 ms 401360 KB Output is correct
21 Correct 990 ms 379532 KB Output is correct
22 Correct 993 ms 396216 KB Output is correct
23 Correct 1008 ms 400132 KB Output is correct
24 Correct 1045 ms 400992 KB Output is correct
25 Correct 1107 ms 401220 KB Output is correct
26 Correct 1065 ms 401224 KB Output is correct
27 Correct 1102 ms 401348 KB Output is correct
28 Correct 1095 ms 401348 KB Output is correct
29 Correct 1061 ms 401280 KB Output is correct
30 Correct 1048 ms 401264 KB Output is correct
31 Correct 1060 ms 401196 KB Output is correct
32 Correct 1103 ms 401220 KB Output is correct
33 Correct 1053 ms 401360 KB Output is correct
34 Correct 1099 ms 401344 KB Output is correct
35 Correct 1096 ms 401340 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 5097 ms 426700 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 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 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 4311 ms 40848 KB Output is correct
21 Correct 4567 ms 40980 KB Output is correct
22 Correct 4432 ms 40876 KB Output is correct
23 Correct 4305 ms 41052 KB Output is correct
24 Correct 4298 ms 40840 KB Output is correct
25 Correct 4267 ms 40844 KB Output is correct
26 Correct 4361 ms 40840 KB Output is correct
27 Correct 4428 ms 40944 KB Output is correct
28 Correct 4431 ms 40872 KB Output is correct
29 Correct 4331 ms 40856 KB Output is correct
30 Correct 4866 ms 41208 KB Output is correct
31 Correct 3805 ms 40872 KB Output is correct
32 Correct 2646 ms 41608 KB Output is correct
33 Correct 4539 ms 40824 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 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 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1027 ms 401360 KB Output is correct
21 Correct 990 ms 379532 KB Output is correct
22 Correct 993 ms 396216 KB Output is correct
23 Correct 1008 ms 400132 KB Output is correct
24 Correct 1045 ms 400992 KB Output is correct
25 Correct 1107 ms 401220 KB Output is correct
26 Correct 1065 ms 401224 KB Output is correct
27 Correct 1102 ms 401348 KB Output is correct
28 Correct 1095 ms 401348 KB Output is correct
29 Correct 1061 ms 401280 KB Output is correct
30 Correct 1048 ms 401264 KB Output is correct
31 Correct 1060 ms 401196 KB Output is correct
32 Correct 1103 ms 401220 KB Output is correct
33 Correct 1053 ms 401360 KB Output is correct
34 Correct 1099 ms 401344 KB Output is correct
35 Correct 1096 ms 401340 KB Output is correct
36 Correct 1468 ms 402084 KB Output is correct
37 Correct 1254 ms 380616 KB Output is correct
38 Correct 1330 ms 397000 KB Output is correct
39 Correct 1385 ms 401068 KB Output is correct
40 Correct 1397 ms 401812 KB Output is correct
41 Correct 1395 ms 401808 KB Output is correct
42 Correct 1465 ms 401904 KB Output is correct
43 Correct 1539 ms 402080 KB Output is correct
44 Correct 1207 ms 402120 KB Output is correct
45 Correct 1147 ms 402084 KB Output is correct
46 Correct 1408 ms 402000 KB Output is correct
47 Correct 1477 ms 402116 KB Output is correct
48 Correct 1389 ms 402028 KB Output is correct
49 Correct 1385 ms 402032 KB Output is correct
50 Correct 1104 ms 402268 KB Output is correct
51 Correct 1164 ms 401988 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 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 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1027 ms 401360 KB Output is correct
21 Correct 990 ms 379532 KB Output is correct
22 Correct 993 ms 396216 KB Output is correct
23 Correct 1008 ms 400132 KB Output is correct
24 Correct 1045 ms 400992 KB Output is correct
25 Correct 1107 ms 401220 KB Output is correct
26 Correct 1065 ms 401224 KB Output is correct
27 Correct 1102 ms 401348 KB Output is correct
28 Correct 1095 ms 401348 KB Output is correct
29 Correct 1061 ms 401280 KB Output is correct
30 Correct 1048 ms 401264 KB Output is correct
31 Correct 1060 ms 401196 KB Output is correct
32 Correct 1103 ms 401220 KB Output is correct
33 Correct 1053 ms 401360 KB Output is correct
34 Correct 1099 ms 401344 KB Output is correct
35 Correct 1096 ms 401340 KB Output is correct
36 Correct 0 ms 348 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 5097 ms 426700 KB Time limit exceeded
40 Halted 0 ms 0 KB -