oj.uz

Submission #336338

# Submission time Handle Problem Language Result Execution time Memory
336338 2020-12-15T05:11:32 Z 12tqian Bridges (APIO19_bridges) C++17
73 / 100
 3000 ms 10232 KB 
#include <bits/stdc++.h>

struct DSU {
    std::vector<int> e;
    void init(int n) {
        e = std::vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};
namespace output {
    using namespace std;
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    // void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    // void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    template<class T> void pr(const complex<T>& x) { cout << x; }
    template<class T1, class T2> void pr(const pair<T1, T2>& x);
    template<class T> void pr(const T& x);
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) {
        pr(t); pr(ts...); }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{", x.f, ", ", x.s, "}"); }
    template<class T> void pr(const T& x) {
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst ? ", " : "", a), fst = 0;
        pr("}"); }
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) {
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); }
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) {
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); }
}


using namespace output;
int main() {
    const int B = 800;
    const int INF = 1e9;
    using namespace std;
    ios_base::sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<array<int, 3>> ed;
    vector<int> id(m);
    iota(id.begin(), id.end(), 0);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        ed.push_back({u, v, w});
    }
    
    vector<int> mod(m);
    int q; cin >> q;
    vector<array<int, 3>> modify;
    vector<array<int, 3>> queries;
    vector<int> vis(n);
    vector<int> rem;
    vector<array<int, 2>> ans;
    vector<int> change(m, -1);
    vector<int> todo;
    DSU D;
    for (int i = 0; i < q; i++) {
        int x, y, z; cin >> x >> y >> z;
        y--;
        if (x == 1) 
            modify.push_back({y, z, i});
        else 
            queries.push_back({y, z, i});
        if (i == q - 1 || int(modify.size()) + int(queries.size()) == B) {
            sort(id.begin(), id.end(), [&ed](int& x, int & y) {
                return ed[x][2] < ed[y][2];
            }); 
            D.init(n);
            sort(queries.begin(), queries.end(), [](array<int, 3>& a, array<int, 3>& b) {
                return a[1] > b[1];
            });
            for (auto& mm : modify) 
                mod[mm[0]] = 1;
            int it = m;
            for (auto& qq : queries) {
                int weight = qq[1];
                int ti = qq[2];
                while (it && ed[id[it - 1]][2] >= weight) {
                    it--;
                    if (!mod[id[it]]) 
                        D.unite(ed[id[it]][0], ed[id[it]][1]);
                }
                for (auto& mm : modify) { 
                    todo.push_back(mm[0]);
                    if (mm[2] < ti) 
                        change[mm[0]] = mm[1];
                }
                for (auto& t : todo) {
                    if (change[t] == -1) {
                        if (ed[t][2] >= weight) {
                            int u = D.get(ed[t][0]);
                            int v = D.get(ed[t][1]);
                            adj[u].push_back(v);
                            adj[v].push_back(u);
                        }
                    } else {
                        if (change[t] >= weight) {
                            int u = D.get(ed[t][0]);
                            int v = D.get(ed[t][1]);
                            adj[u].push_back(v);
                            adj[v].push_back(u);
                        }
                    }
                }
                int res = 0;
                function<void(int)> dfs = [&](int src) {
                    vis[src] = 1;
                    res += D.size(src);
                    rem.push_back(src);
                    for (int nxt : adj[src]) {
                        if (vis[nxt])
                            continue;
                        dfs(nxt);
                    }
                };
                dfs(D.get(qq[0]));
                ans.push_back({ti, res});
                for (auto& r : rem)
                    vis[r] = 0;
                for (auto& t : todo) 
                    change[t] = -1;
                for (auto& t : todo) {
                    int u = D.get(ed[t][0]);
                    int v = D.get(ed[t][1]);
                    adj[u].clear();
                    adj[v].clear();
                }
                rem.clear();
                todo.clear();
            }
            for (auto& mm : modify)
                mod[mm[0]] = 0, ed[mm[0]][2] = mm[1];
            queries.clear();
            modify.clear();
        }
    }
    sort(ans.begin(), ans.end());
    for (auto& a : ans) 
        cout << a[1] << '\n';
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:63:15: warning: unused variable 'INF' [-Wunused-variable]
   63 |     const int INF = 1e9;
      |               ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 92 ms 520 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 60 ms 620 KB Output is correct
6 Correct 56 ms 620 KB Output is correct
7 Correct 62 ms 576 KB Output is correct
8 Correct 58 ms 620 KB Output is correct
9 Correct 78 ms 620 KB Output is correct
10 Correct 55 ms 620 KB Output is correct
11 Correct 54 ms 620 KB Output is correct
12 Correct 68 ms 768 KB Output is correct
13 Correct 64 ms 620 KB Output is correct
14 Correct 58 ms 620 KB Output is correct
15 Correct 81 ms 620 KB Output is correct
16 Correct 65 ms 620 KB Output is correct
17 Correct 63 ms 620 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1880 ms 5668 KB Output is correct
2 Correct 1886 ms 8268 KB Output is correct
3 Correct 1918 ms 8360 KB Output is correct
4 Correct 1915 ms 8232 KB Output is correct
5 Correct 1886 ms 8236 KB Output is correct
6 Correct 2947 ms 7412 KB Output is correct
7 Correct 2655 ms 7512 KB Output is correct
8 Correct 2548 ms 7456 KB Output is correct
9 Correct 55 ms 2944 KB Output is correct
10 Correct 2126 ms 7344 KB Output is correct
11 Correct 1889 ms 7464 KB Output is correct
12 Correct 1456 ms 7588 KB Output is correct
13 Correct 1402 ms 7140 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1501 ms 4044 KB Output is correct
2 Correct 1525 ms 3592 KB Output is correct
3 Correct 1965 ms 6396 KB Output is correct
4 Correct 1544 ms 6324 KB Output is correct
5 Correct 54 ms 2796 KB Output is correct
6 Correct 1694 ms 6152 KB Output is correct
7 Correct 1420 ms 6128 KB Output is correct
8 Correct 1279 ms 6328 KB Output is correct
9 Correct 920 ms 6188 KB Output is correct
10 Correct 798 ms 5984 KB Output is correct
11 Correct 951 ms 5936 KB Output is correct
12 Correct 835 ms 6060 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 6452 KB Output is correct
2 Correct 52 ms 1520 KB Output is correct
3 Correct 126 ms 3040 KB Output is correct
4 Correct 80 ms 2912 KB Output is correct
5 Correct 810 ms 6508 KB Output is correct
6 Correct 1081 ms 6440 KB Output is correct
7 Correct 790 ms 6612 KB Output is correct
8 Correct 572 ms 4812 KB Output is correct
9 Correct 545 ms 4836 KB Output is correct
10 Correct 543 ms 4832 KB Output is correct
11 Correct 888 ms 5664 KB Output is correct
12 Correct 871 ms 5856 KB Output is correct
13 Correct 894 ms 6064 KB Output is correct
14 Correct 738 ms 6496 KB Output is correct
15 Correct 772 ms 6496 KB Output is correct
16 Correct 1128 ms 6368 KB Output is correct
17 Correct 1151 ms 6492 KB Output is correct
18 Correct 1147 ms 6368 KB Output is correct
19 Correct 1145 ms 6456 KB Output is correct
20 Correct 1088 ms 6240 KB Output is correct
21 Correct 1020 ms 6240 KB Output is correct
22 Correct 1137 ms 6368 KB Output is correct
23 Correct 876 ms 5992 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1880 ms 5668 KB Output is correct
2 Correct 1886 ms 8268 KB Output is correct
3 Correct 1918 ms 8360 KB Output is correct
4 Correct 1915 ms 8232 KB Output is correct
5 Correct 1886 ms 8236 KB Output is correct
6 Correct 2947 ms 7412 KB Output is correct
7 Correct 2655 ms 7512 KB Output is correct
8 Correct 2548 ms 7456 KB Output is correct
9 Correct 55 ms 2944 KB Output is correct
10 Correct 2126 ms 7344 KB Output is correct
11 Correct 1889 ms 7464 KB Output is correct
12 Correct 1456 ms 7588 KB Output is correct
13 Correct 1402 ms 7140 KB Output is correct
14 Correct 1501 ms 4044 KB Output is correct
15 Correct 1525 ms 3592 KB Output is correct
16 Correct 1965 ms 6396 KB Output is correct
17 Correct 1544 ms 6324 KB Output is correct
18 Correct 54 ms 2796 KB Output is correct
19 Correct 1694 ms 6152 KB Output is correct
20 Correct 1420 ms 6128 KB Output is correct
21 Correct 1279 ms 6328 KB Output is correct
22 Correct 920 ms 6188 KB Output is correct
23 Correct 798 ms 5984 KB Output is correct
24 Correct 951 ms 5936 KB Output is correct
25 Correct 835 ms 6060 KB Output is correct
26 Correct 1858 ms 7972 KB Output is correct
27 Correct 2483 ms 8008 KB Output is correct
28 Correct 1992 ms 7964 KB Output is correct
29 Correct 1447 ms 7908 KB Output is correct
30 Correct 2292 ms 7888 KB Output is correct
31 Correct 2342 ms 8040 KB Output is correct
32 Correct 2360 ms 7932 KB Output is correct
33 Correct 1896 ms 8116 KB Output is correct
34 Correct 1965 ms 8136 KB Output is correct
35 Correct 1963 ms 8360 KB Output is correct
36 Correct 1507 ms 8036 KB Output is correct
37 Correct 1505 ms 7924 KB Output is correct
38 Correct 1483 ms 8040 KB Output is correct
39 Correct 1077 ms 7724 KB Output is correct
40 Correct 1088 ms 7936 KB Output is correct
41 Correct 1075 ms 7648 KB Output is correct
42 Correct 1033 ms 7908 KB Output is correct
43 Correct 1026 ms 7780 KB Output is correct
44 Correct 998 ms 7576 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 92 ms 520 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 60 ms 620 KB Output is correct
6 Correct 56 ms 620 KB Output is correct
7 Correct 62 ms 576 KB Output is correct
8 Correct 58 ms 620 KB Output is correct
9 Correct 78 ms 620 KB Output is correct
10 Correct 55 ms 620 KB Output is correct
11 Correct 54 ms 620 KB Output is correct
12 Correct 68 ms 768 KB Output is correct
13 Correct 64 ms 620 KB Output is correct
14 Correct 58 ms 620 KB Output is correct
15 Correct 81 ms 620 KB Output is correct
16 Correct 65 ms 620 KB Output is correct
17 Correct 63 ms 620 KB Output is correct
18 Correct 1880 ms 5668 KB Output is correct
19 Correct 1886 ms 8268 KB Output is correct
20 Correct 1918 ms 8360 KB Output is correct
21 Correct 1915 ms 8232 KB Output is correct
22 Correct 1886 ms 8236 KB Output is correct
23 Correct 2947 ms 7412 KB Output is correct
24 Correct 2655 ms 7512 KB Output is correct
25 Correct 2548 ms 7456 KB Output is correct
26 Correct 55 ms 2944 KB Output is correct
27 Correct 2126 ms 7344 KB Output is correct
28 Correct 1889 ms 7464 KB Output is correct
29 Correct 1456 ms 7588 KB Output is correct
30 Correct 1402 ms 7140 KB Output is correct
31 Correct 1501 ms 4044 KB Output is correct
32 Correct 1525 ms 3592 KB Output is correct
33 Correct 1965 ms 6396 KB Output is correct
34 Correct 1544 ms 6324 KB Output is correct
35 Correct 54 ms 2796 KB Output is correct
36 Correct 1694 ms 6152 KB Output is correct
37 Correct 1420 ms 6128 KB Output is correct
38 Correct 1279 ms 6328 KB Output is correct
39 Correct 920 ms 6188 KB Output is correct
40 Correct 798 ms 5984 KB Output is correct
41 Correct 951 ms 5936 KB Output is correct
42 Correct 835 ms 6060 KB Output is correct
43 Correct 1071 ms 6452 KB Output is correct
44 Correct 52 ms 1520 KB Output is correct
45 Correct 126 ms 3040 KB Output is correct
46 Correct 80 ms 2912 KB Output is correct
47 Correct 810 ms 6508 KB Output is correct
48 Correct 1081 ms 6440 KB Output is correct
49 Correct 790 ms 6612 KB Output is correct
50 Correct 572 ms 4812 KB Output is correct
51 Correct 545 ms 4836 KB Output is correct
52 Correct 543 ms 4832 KB Output is correct
53 Correct 888 ms 5664 KB Output is correct
54 Correct 871 ms 5856 KB Output is correct
55 Correct 894 ms 6064 KB Output is correct
56 Correct 738 ms 6496 KB Output is correct
57 Correct 772 ms 6496 KB Output is correct
58 Correct 1128 ms 6368 KB Output is correct
59 Correct 1151 ms 6492 KB Output is correct
60 Correct 1147 ms 6368 KB Output is correct
61 Correct 1145 ms 6456 KB Output is correct
62 Correct 1088 ms 6240 KB Output is correct
63 Correct 1020 ms 6240 KB Output is correct
64 Correct 1137 ms 6368 KB Output is correct
65 Correct 876 ms 5992 KB Output is correct
66 Correct 1858 ms 7972 KB Output is correct
67 Correct 2483 ms 8008 KB Output is correct
68 Correct 1992 ms 7964 KB Output is correct
69 Correct 1447 ms 7908 KB Output is correct
70 Correct 2292 ms 7888 KB Output is correct
71 Correct 2342 ms 8040 KB Output is correct
72 Correct 2360 ms 7932 KB Output is correct
73 Correct 1896 ms 8116 KB Output is correct
74 Correct 1965 ms 8136 KB Output is correct
75 Correct 1963 ms 8360 KB Output is correct
76 Correct 1507 ms 8036 KB Output is correct
77 Correct 1505 ms 7924 KB Output is correct
78 Correct 1483 ms 8040 KB Output is correct
79 Correct 1077 ms 7724 KB Output is correct
80 Correct 1088 ms 7936 KB Output is correct
81 Correct 1075 ms 7648 KB Output is correct
82 Correct 1033 ms 7908 KB Output is correct
83 Correct 1026 ms 7780 KB Output is correct
84 Correct 998 ms 7576 KB Output is correct
85 Correct 2963 ms 10080 KB Output is correct
86 Correct 303 ms 4832 KB Output is correct
87 Correct 203 ms 4832 KB Output is correct
88 Correct 2126 ms 8460 KB Output is correct
89 Correct 2979 ms 10232 KB Output is correct
90 Correct 2087 ms 8392 KB Output is correct
91 Correct 1928 ms 8036 KB Output is correct
92 Correct 1910 ms 8164 KB Output is correct
93 Correct 2498 ms 7400 KB Output is correct
94 Correct 2478 ms 9204 KB Output is correct
95 Correct 2553 ms 9376 KB Output is correct
96 Correct 2672 ms 8440 KB Output is correct
97 Correct 1262 ms 8996 KB Output is correct
98 Correct 1362 ms 8160 KB Output is correct
99 Execution timed out 3026 ms 10108 KB Time limit exceeded
100 Halted 0 ms 0 KB -