oj.uz

Submission #709140

# Submission time Handle Problem Language Result Execution time Memory
709140 2023-03-13T06:40:36 Z resting Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 1871 ms 71520 KB 
#include <bits/stdc++.h>

using namespace std;


#define int long long

const int mx = 500 + 5;

vector<int> adj[mx];
vector<int> w[mx];
vector<pair<int, pair<int, int>>> edges;

int delu, delv;
int dfs(int v, int p, int b) { //returns -1 if not found, else min edge
    //cout << "dfs " << v << ","<<b<<endl;
    for (int i = 0; i < adj[v].size(); i++) {
        auto& x = adj[v][i];
        if (x == p) continue;
        if (x == b) {
            delu = v; delv = x;
            return w[v][i];
        }
        int t = dfs(x, v, b);
        if (t != -1) {
            if (w[v][i] < t) {
                delu = v; delv = x;
            }
            return min(t, w[v][i]);
        }
    }
    return -1;
}

int32_t main() {
   // cout << "tesT" << endl;
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M;
    edges.resize(M);
    for (auto& x : edges) {
        cin >> x.second.first >> x.second.second >> x.first;
    }

    int Q; cin >> Q;
    vector<int> q(Q); for (auto& x : q) cin >> x;
    sort(edges.begin(), edges.end());
    vector<pair<int, pair<int, int>>> upd;
    for (auto& x : q)
        upd.push_back({ x, {5, -1} });
    auto ad = [&](int u, int v, int ww) {
        adj[u].push_back(v);
        adj[v].push_back(u);
        w[u].push_back(ww);
        w[v].push_back(ww);
    };
    auto del = [&](int u, int v) {
        auto a = find(adj[u].begin(), adj[u].end(), v) - adj[u].begin();
        auto b = find(adj[v].begin(), adj[v].end(), u) - adj[v].begin();
      //  cout << a << "," << adj[u].size() << "," << b << "," << adj[v].size() << endl;
        adj[u].erase(adj[u].begin() + a);
        w[u].erase(w[u].begin() + a);
        adj[v].erase(adj[v].begin() + b);
        w[v].erase(w[v].begin() + b);
    };
    for (int i = 0; i < edges.size(); i++) {
        int t = dfs(edges[i].second.first, -1, edges[i].second.second);
        int m = (t + edges[i].first + 1) / 2;
        if (t == -1) m = -1;
       // cout <<"a"<< edges[i].first<<","<<t << endl;
        if(t != -1)
        upd.push_back({ m, {1LL, m - t} }); //remove increasing
        upd.push_back({ m, {2LL, edges[i].first - m} }); //add decreasing
        upd.push_back({ edges[i].first, {3LL, 0} }); // remove decreasing
        upd.push_back({ edges[i].first, {4LL, 0} }); //add increasing


        if (t != -1) {
           // cout << i << "," << t << endl;
            del(delu, delv);
        }
        ad(edges[i].second.first, edges[i].second.second, edges[i].first);
    }
    for (int i = 0; i < N; i++) {
        adj[i].clear(); w[i].clear();
    }

    //do in reverse
    //reverse(edges.begin(), edges.end());
    //for (int i = 0; i < edges.size(); i++) {
    //    int t = dfs(edges[i].second.first, -1, edges[i].second.second);
    //    ub[edges.size() - i - 1] =1e9- t;
    //    if (t != -1) {
    //        del(delu, delv);
    //    }
    //    ad(edges[i].second.first, edges[i].second.second, 1e9-edges[i].first);
    //}

    //reverse(edges.begin(), edges.end());

    sort(upd.begin(), upd.end());
    int prev = upd.front().first;
    int m = 0, b = 0;
    for (auto& x : upd) {
       // cout << x.first << "," << x.second.first << "," << x.second.second << endl;
        m += b * (x.first - prev); prev = x.first;
        if (x.second.first == 5) {
            cout << m << endl;
        }
        else if (x.second.first == 1) {
            m -= x.second.second;
            b--;
        }
        else if (x.second.first == 2) {
            m += x.second.second;
            b--;
        }
        else if (x.second.first == 3) {
            b++;
        }
        else if (x.second.first == 4) {
            b++;
        }
    }


}

Compilation message

reconstruction.cpp: In function 'long long int dfs(long long int, long long int, long long int)':
reconstruction.cpp:17:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:65:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 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 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 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 448 ms 16872 KB Output is correct
21 Correct 223 ms 16832 KB Output is correct
22 Correct 368 ms 16776 KB Output is correct
23 Correct 350 ms 16932 KB Output is correct
24 Correct 349 ms 16868 KB Output is correct
25 Correct 416 ms 16904 KB Output is correct
26 Correct 419 ms 16896 KB Output is correct
27 Correct 404 ms 16956 KB Output is correct
28 Correct 428 ms 16860 KB Output is correct
29 Correct 312 ms 16960 KB Output is correct
30 Correct 435 ms 16816 KB Output is correct
31 Correct 405 ms 16840 KB Output is correct
32 Correct 415 ms 16912 KB Output is correct
33 Correct 414 ms 16928 KB Output is correct
34 Correct 315 ms 18408 KB Output is correct
35 Correct 459 ms 16784 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1659 ms 71236 KB Output is correct
5 Correct 1670 ms 71236 KB Output is correct
6 Correct 1725 ms 71408 KB Output is correct
7 Correct 1459 ms 71272 KB Output is correct
8 Correct 1485 ms 71324 KB Output is correct
9 Correct 1468 ms 71304 KB Output is correct
10 Correct 1797 ms 71360 KB Output is correct
11 Correct 1515 ms 71400 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 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 1381 ms 53812 KB Output is correct
21 Correct 1330 ms 54108 KB Output is correct
22 Correct 1443 ms 54088 KB Output is correct
23 Correct 1415 ms 53908 KB Output is correct
24 Correct 1423 ms 53864 KB Output is correct
25 Correct 1426 ms 53896 KB Output is correct
26 Correct 1426 ms 53816 KB Output is correct
27 Correct 1469 ms 53816 KB Output is correct
28 Correct 1371 ms 53832 KB Output is correct
29 Correct 1432 ms 53900 KB Output is correct
30 Correct 1410 ms 54076 KB Output is correct
31 Correct 1446 ms 53668 KB Output is correct
32 Correct 1398 ms 54332 KB Output is correct
33 Correct 1423 ms 53700 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 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 448 ms 16872 KB Output is correct
21 Correct 223 ms 16832 KB Output is correct
22 Correct 368 ms 16776 KB Output is correct
23 Correct 350 ms 16932 KB Output is correct
24 Correct 349 ms 16868 KB Output is correct
25 Correct 416 ms 16904 KB Output is correct
26 Correct 419 ms 16896 KB Output is correct
27 Correct 404 ms 16956 KB Output is correct
28 Correct 428 ms 16860 KB Output is correct
29 Correct 312 ms 16960 KB Output is correct
30 Correct 435 ms 16816 KB Output is correct
31 Correct 405 ms 16840 KB Output is correct
32 Correct 415 ms 16912 KB Output is correct
33 Correct 414 ms 16928 KB Output is correct
34 Correct 315 ms 18408 KB Output is correct
35 Correct 459 ms 16784 KB Output is correct
36 Correct 457 ms 17200 KB Output is correct
37 Correct 248 ms 17132 KB Output is correct
38 Correct 371 ms 17084 KB Output is correct
39 Correct 426 ms 17276 KB Output is correct
40 Correct 393 ms 17124 KB Output is correct
41 Correct 441 ms 17248 KB Output is correct
42 Correct 496 ms 17288 KB Output is correct
43 Correct 495 ms 17172 KB Output is correct
44 Correct 466 ms 17192 KB Output is correct
45 Correct 360 ms 17344 KB Output is correct
46 Correct 470 ms 17112 KB Output is correct
47 Correct 453 ms 17120 KB Output is correct
48 Correct 500 ms 17136 KB Output is correct
49 Correct 419 ms 17168 KB Output is correct
50 Correct 384 ms 18720 KB Output is correct
51 Correct 427 ms 17248 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 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 448 ms 16872 KB Output is correct
21 Correct 223 ms 16832 KB Output is correct
22 Correct 368 ms 16776 KB Output is correct
23 Correct 350 ms 16932 KB Output is correct
24 Correct 349 ms 16868 KB Output is correct
25 Correct 416 ms 16904 KB Output is correct
26 Correct 419 ms 16896 KB Output is correct
27 Correct 404 ms 16956 KB Output is correct
28 Correct 428 ms 16860 KB Output is correct
29 Correct 312 ms 16960 KB Output is correct
30 Correct 435 ms 16816 KB Output is correct
31 Correct 405 ms 16840 KB Output is correct
32 Correct 415 ms 16912 KB Output is correct
33 Correct 414 ms 16928 KB Output is correct
34 Correct 315 ms 18408 KB Output is correct
35 Correct 459 ms 16784 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 1659 ms 71236 KB Output is correct
40 Correct 1670 ms 71236 KB Output is correct
41 Correct 1725 ms 71408 KB Output is correct
42 Correct 1459 ms 71272 KB Output is correct
43 Correct 1485 ms 71324 KB Output is correct
44 Correct 1468 ms 71304 KB Output is correct
45 Correct 1797 ms 71360 KB Output is correct
46 Correct 1515 ms 71400 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1381 ms 53812 KB Output is correct
49 Correct 1330 ms 54108 KB Output is correct
50 Correct 1443 ms 54088 KB Output is correct
51 Correct 1415 ms 53908 KB Output is correct
52 Correct 1423 ms 53864 KB Output is correct
53 Correct 1426 ms 53896 KB Output is correct
54 Correct 1426 ms 53816 KB Output is correct
55 Correct 1469 ms 53816 KB Output is correct
56 Correct 1371 ms 53832 KB Output is correct
57 Correct 1432 ms 53900 KB Output is correct
58 Correct 1410 ms 54076 KB Output is correct
59 Correct 1446 ms 53668 KB Output is correct
60 Correct 1398 ms 54332 KB Output is correct
61 Correct 1423 ms 53700 KB Output is correct
62 Correct 457 ms 17200 KB Output is correct
63 Correct 248 ms 17132 KB Output is correct
64 Correct 371 ms 17084 KB Output is correct
65 Correct 426 ms 17276 KB Output is correct
66 Correct 393 ms 17124 KB Output is correct
67 Correct 441 ms 17248 KB Output is correct
68 Correct 496 ms 17288 KB Output is correct
69 Correct 495 ms 17172 KB Output is correct
70 Correct 466 ms 17192 KB Output is correct
71 Correct 360 ms 17344 KB Output is correct
72 Correct 470 ms 17112 KB Output is correct
73 Correct 453 ms 17120 KB Output is correct
74 Correct 500 ms 17136 KB Output is correct
75 Correct 419 ms 17168 KB Output is correct
76 Correct 384 ms 18720 KB Output is correct
77 Correct 427 ms 17248 KB Output is correct
78 Correct 1781 ms 71288 KB Output is correct
79 Correct 1625 ms 71224 KB Output is correct
80 Correct 1793 ms 71188 KB Output is correct
81 Correct 1779 ms 71332 KB Output is correct
82 Correct 1755 ms 71208 KB Output is correct
83 Correct 1846 ms 71240 KB Output is correct
84 Correct 1811 ms 71260 KB Output is correct
85 Correct 1753 ms 71252 KB Output is correct
86 Correct 1822 ms 71240 KB Output is correct
87 Correct 1753 ms 71508 KB Output is correct
88 Correct 1806 ms 71256 KB Output is correct
89 Correct 1861 ms 71216 KB Output is correct
90 Correct 1871 ms 71340 KB Output is correct
91 Correct 1830 ms 71296 KB Output is correct
92 Correct 1681 ms 71520 KB Output is correct
93 Correct 1784 ms 71380 KB Output is correct