oj.uz

Submission #674522

# Submission time Handle Problem Language Result Execution time Memory
674522 2022-12-24T16:52:56 Z someone Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 2485 ms 67468 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Arc {
    int a, b, pds, i;
    
    bool operator <(const Arc& other) const {
        return pds < other.pds;
    }
};
 
struct Req {
    int q, i, add;
};
 
const int Q = 1e6 + 42, N = 542, M = 1e5 + 42, MOD = 1e9 + 7, INF = 1e12 + 42;
 
deque<Req> req;
deque<Arc> arc, mst;
int n, m, q, par[N], ans[Q], deb[M], fin[M], w[M];

int F(int i) {
    if(par[i] < 0)
        return i;
    return par[i] = F(par[i]);
}
 
bool U(int a, int b) {
    a = F(a), b = F(b);
    if(a == b) return false;
    if(-par[a] < -par[b]) swap(a, b);
    
    par[a] += par[b];
    par[b] = a;
    return true;
}
 
set<pair<int, int>> val;

void add(Arc edge) {
    for(int i = 0; i < n; i++)
        par[i] = -1;
    U(edge.a, edge.b);
    for(int i = 0; i < n-1; i++) {
        if(!U(mst[i].a, mst[i].b)) {
            int mid = (edge.pds + mst[i].pds) >> 1;
            fin[edge.i] = mid;
            if(mst[i].i != -1)
                deb[mst[i].i] = mid;
            mst.erase(mst.begin() + i);
            break;
        }
    }
    mst.push_front(edge);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    mt19937 rng(42);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b >> w[i];
        a--, b--;
        arc.push_back({a, b, w[i] << 1, i});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        int rq; cin >> rq;
        req.push_back({rq << 1, i, 0});
    }
    
    for(int i = 1; i < n; i++)
        mst.push_back({i-1, i, INF, -1});
    sort(arc.begin(), arc.end());
    for(int i = m-1; i >= 0 && !req.empty(); i--)
        add(arc[i]);
        
    for(int i = 0; i < m; i++) {
        req.push_back({deb[i], -1, w[i]});
        req.push_back({fin[i], -1, -w[i]});
    }
    
    sort(req.begin(), req.end(),
    [](Req a, Req b) {
        if(a.q == b.q) {
            if(a.i == b.i)
                return a.add > b.add;
            return a.i < b.i;
        }
        return a.q < b.q;
    });
    
    vector<int> mst;
    for(Req r : req) {
        if(r.i == -1) {
            if(r.add > 0) {
                mst.push_back(r.add);
            } else {
                int sz = mst.size();
                for(int i = 0; i < sz; i++)
                    if(mst[i] == -r.add) {
                        mst.erase(mst.begin() + i);
                        break;
                    }
            }
        } else {
            r.q >>= 1;
            for(int i : mst)
                ans[r.i] += abs(i - r.q);
        }
    }
    
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 642 ms 12552 KB Output is correct
21 Correct 383 ms 12580 KB Output is correct
22 Correct 393 ms 12548 KB Output is correct
23 Correct 423 ms 12540 KB Output is correct
24 Correct 512 ms 12548 KB Output is correct
25 Correct 604 ms 12552 KB Output is correct
26 Correct 631 ms 12552 KB Output is correct
27 Correct 635 ms 12584 KB Output is correct
28 Correct 621 ms 12456 KB Output is correct
29 Correct 727 ms 12788 KB Output is correct
30 Correct 629 ms 12492 KB Output is correct
31 Correct 628 ms 12644 KB Output is correct
32 Correct 625 ms 12552 KB Output is correct
33 Correct 622 ms 12484 KB Output is correct
34 Correct 1827 ms 13844 KB Output is correct
35 Correct 634 ms 12552 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1146 ms 57476 KB Output is correct
5 Correct 1090 ms 65224 KB Output is correct
6 Correct 1060 ms 65272 KB Output is correct
7 Correct 854 ms 67112 KB Output is correct
8 Correct 779 ms 67316 KB Output is correct
9 Correct 799 ms 67468 KB Output is correct
10 Correct 1247 ms 65296 KB Output is correct
11 Correct 869 ms 67412 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 779 ms 47076 KB Output is correct
21 Correct 796 ms 54544 KB Output is correct
22 Correct 810 ms 54500 KB Output is correct
23 Correct 829 ms 54432 KB Output is correct
24 Correct 701 ms 54544 KB Output is correct
25 Correct 837 ms 54480 KB Output is correct
26 Correct 730 ms 54516 KB Output is correct
27 Correct 843 ms 54524 KB Output is correct
28 Correct 720 ms 54476 KB Output is correct
29 Correct 818 ms 54364 KB Output is correct
30 Correct 851 ms 54768 KB Output is correct
31 Correct 704 ms 54340 KB Output is correct
32 Correct 706 ms 55040 KB Output is correct
33 Correct 894 ms 54392 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 642 ms 12552 KB Output is correct
21 Correct 383 ms 12580 KB Output is correct
22 Correct 393 ms 12548 KB Output is correct
23 Correct 423 ms 12540 KB Output is correct
24 Correct 512 ms 12548 KB Output is correct
25 Correct 604 ms 12552 KB Output is correct
26 Correct 631 ms 12552 KB Output is correct
27 Correct 635 ms 12584 KB Output is correct
28 Correct 621 ms 12456 KB Output is correct
29 Correct 727 ms 12788 KB Output is correct
30 Correct 629 ms 12492 KB Output is correct
31 Correct 628 ms 12644 KB Output is correct
32 Correct 625 ms 12552 KB Output is correct
33 Correct 622 ms 12484 KB Output is correct
34 Correct 1827 ms 13844 KB Output is correct
35 Correct 634 ms 12552 KB Output is correct
36 Correct 649 ms 13484 KB Output is correct
37 Correct 407 ms 13612 KB Output is correct
38 Correct 400 ms 13488 KB Output is correct
39 Correct 455 ms 13488 KB Output is correct
40 Correct 532 ms 13488 KB Output is correct
41 Correct 626 ms 13520 KB Output is correct
42 Correct 651 ms 13556 KB Output is correct
43 Correct 661 ms 13516 KB Output is correct
44 Correct 636 ms 13516 KB Output is correct
45 Correct 739 ms 13924 KB Output is correct
46 Correct 652 ms 13516 KB Output is correct
47 Correct 658 ms 13484 KB Output is correct
48 Correct 653 ms 13488 KB Output is correct
49 Correct 658 ms 13536 KB Output is correct
50 Correct 1799 ms 14668 KB Output is correct
51 Correct 644 ms 13492 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 642 ms 12552 KB Output is correct
21 Correct 383 ms 12580 KB Output is correct
22 Correct 393 ms 12548 KB Output is correct
23 Correct 423 ms 12540 KB Output is correct
24 Correct 512 ms 12548 KB Output is correct
25 Correct 604 ms 12552 KB Output is correct
26 Correct 631 ms 12552 KB Output is correct
27 Correct 635 ms 12584 KB Output is correct
28 Correct 621 ms 12456 KB Output is correct
29 Correct 727 ms 12788 KB Output is correct
30 Correct 629 ms 12492 KB Output is correct
31 Correct 628 ms 12644 KB Output is correct
32 Correct 625 ms 12552 KB Output is correct
33 Correct 622 ms 12484 KB Output is correct
34 Correct 1827 ms 13844 KB Output is correct
35 Correct 634 ms 12552 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1146 ms 57476 KB Output is correct
40 Correct 1090 ms 65224 KB Output is correct
41 Correct 1060 ms 65272 KB Output is correct
42 Correct 854 ms 67112 KB Output is correct
43 Correct 779 ms 67316 KB Output is correct
44 Correct 799 ms 67468 KB Output is correct
45 Correct 1247 ms 65296 KB Output is correct
46 Correct 869 ms 67412 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 779 ms 47076 KB Output is correct
49 Correct 796 ms 54544 KB Output is correct
50 Correct 810 ms 54500 KB Output is correct
51 Correct 829 ms 54432 KB Output is correct
52 Correct 701 ms 54544 KB Output is correct
53 Correct 837 ms 54480 KB Output is correct
54 Correct 730 ms 54516 KB Output is correct
55 Correct 843 ms 54524 KB Output is correct
56 Correct 720 ms 54476 KB Output is correct
57 Correct 818 ms 54364 KB Output is correct
58 Correct 851 ms 54768 KB Output is correct
59 Correct 704 ms 54340 KB Output is correct
60 Correct 706 ms 55040 KB Output is correct
61 Correct 894 ms 54392 KB Output is correct
62 Correct 649 ms 13484 KB Output is correct
63 Correct 407 ms 13612 KB Output is correct
64 Correct 400 ms 13488 KB Output is correct
65 Correct 455 ms 13488 KB Output is correct
66 Correct 532 ms 13488 KB Output is correct
67 Correct 626 ms 13520 KB Output is correct
68 Correct 651 ms 13556 KB Output is correct
69 Correct 661 ms 13516 KB Output is correct
70 Correct 636 ms 13516 KB Output is correct
71 Correct 739 ms 13924 KB Output is correct
72 Correct 652 ms 13516 KB Output is correct
73 Correct 658 ms 13484 KB Output is correct
74 Correct 653 ms 13488 KB Output is correct
75 Correct 658 ms 13536 KB Output is correct
76 Correct 1799 ms 14668 KB Output is correct
77 Correct 644 ms 13492 KB Output is correct
78 Correct 1334 ms 63836 KB Output is correct
79 Correct 1028 ms 65640 KB Output is correct
80 Correct 1022 ms 64800 KB Output is correct
81 Correct 1067 ms 64540 KB Output is correct
82 Correct 1169 ms 63084 KB Output is correct
83 Correct 1230 ms 62980 KB Output is correct
84 Correct 1255 ms 63144 KB Output is correct
85 Correct 1278 ms 62880 KB Output is correct
86 Correct 1266 ms 63060 KB Output is correct
87 Correct 1440 ms 65120 KB Output is correct
88 Correct 1279 ms 63072 KB Output is correct
89 Correct 1273 ms 62780 KB Output is correct
90 Correct 1271 ms 63072 KB Output is correct
91 Correct 1246 ms 62976 KB Output is correct
92 Correct 2485 ms 67412 KB Output is correct
93 Correct 1416 ms 63316 KB Output is correct