oj.uz

답안 #699784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699784 2023-02-18T02:29:20 Z badont 다리 (APIO19_bridges) C++17
100 / 100
 2256 ms 18948 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <utility>
#include <array>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<ll,ll>;
using ld = long double;
using vi = vector<int>;

struct RollbackUF {
	vi e; vector<pii> st;
	RollbackUF(int n) : e(n, -1) {}
	int size(int x) { return -e[find(x)]; }
	int find(int x) { return e[x] < 0 ? x : find(e[x]); }
	int time() { return sz(st); }
	void rollback(int t) {
		for (int i = time(); i --> t;)
			e[st[i].first] = st[i].second;
		st.resize(t);
	}
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return false;
		if (e[a] > e[b]) swap(a, b);
		st.push_back({a, e[a]});
		st.push_back({b, e[b]});
		e[a] += e[b]; e[b] = a;
		return true;
	}
};

void solve() {
    ll n, m;
    cin >> n >> m;

    vector<array<ll, 3>> edges(m);
    for (auto& [x, y, d] : edges) {
        cin >> x >> y >> d;
        x--; y--;
        d = -d;
    }

    ll q; cin >> q;
    const int B = 1000;
    vector<array<ll, 3>> queries_input(q);
    for (auto& [T, b, r] : queries_input) {
        cin >> T >> b >> r;
        b--;
        r = -r;
    }

    const vector queries = queries_input;

    vector<ll> ans(q, -1);

    vector<bool> visited_query(q, false);
    for (ll qid = 0; qid < q; qid += B) {
        vector<int> process;
        vector<bool> changed_edges(m, false);
        vector<int> change_list;
        vector change_times(m, vector<ll>());
        for (ll i = qid; i < min(qid + B, q); i++) {
            process.emplace_back(i);
            visited_query[i] = true;
        }

        for (auto query_idx : process) {
            auto [type, r, b] = queries[query_idx];
            if (type == 1) {
                changed_edges[r] = true;
                change_times[r].pb(query_idx);
                change_list.pb(r);
            }
        }

        sort(all(change_list));
        change_list.erase(unique(all(change_list)), change_list.end());

        vector<int> unchanged_indices;
        for (int i = 0; i < m; i++) if (!changed_edges[i]) {
            unchanged_indices.pb(i);
        }

        sort(all(unchanged_indices), [&](int a, int b) {
            return edges[a][2] < edges[b][2];
        });

        debug(unchanged_indices);

        //must process all edges in --> increasing order
        sort(all(process), [&](int a, int b) {
            //if (queries[a][2] == queries[b][2]) return queries[a][0] < queries[b][0];
            return queries[a][2] < queries[b][2];
        });

        debug(process);

        auto get_weight = [&](int unchanged_index) -> ll {
            return edges[unchanged_indices[unchanged_index]][2];
        };

        int unchanged_ptr = 0;
        RollbackUF dsu(n);
        for (int i = 0; i < process.size(); i++) {
            int u = process[i];
            auto [T, r, b] = queries[u];
            
            while (unchanged_ptr < (int)unchanged_indices.size() and get_weight(unchanged_ptr) <= b) {
                auto [e1, e2, w1] = edges[unchanged_indices[unchanged_ptr]];
                assert(w1 <= b);
                dsu.join(e1, e2);
                unchanged_ptr++;
            }

            int rollback_time = dsu.time();
            
            if (T == 1) {
            } else {
                for (auto edge_num : change_list) {
                    assert(edge_num >= 0 and edge_num < m);
                    auto [p1, p2, original_weight] = edges[edge_num];
                    ll max_less = -1;
                    for (auto query_idx : change_times[edge_num]) if (query_idx < u) {
                        max_less = max(max_less, query_idx);
                    }
                    if (max_less != -1) {
                        auto [T2, edge_point, new_weight] = queries[max_less];
                        assert(T2 == 1 and edge_point == edge_num and max_less < u);
                        if (new_weight <= b) dsu.join(p1, p2);
                    } else {
                        if (original_weight <= b) dsu.join(p1, p2);
                    }
                }
                ans[u] = dsu.size(r);
            }
            dsu.rollback(rollback_time);
        }
        
        //update edges to be relevant
        sort(all(process));
        for (auto query_idx : process) {
            auto [type, b, r] = queries[query_idx];
            assert(r < 0);
            if (type == 1) {
                edges[b][2] = r;
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int u = ans[i];
        assert(visited_query[i]);
        
        if (queries[i][0] == 2) assert(u != -1);

        if (u != -1) {
            assert(queries[i][0] == 2);
            //assert(u < n);
            cout << u << '\n';
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;   
}

Compilation message

bridges.cpp: In function 'void solve()':
bridges.cpp:31:20: warning: statement has no effect [-Wunused-value]
   31 | #define debug(...) "zzz"
      |                    ^~~~~
bridges.cpp:120:9: note: in expansion of macro 'debug'
  120 |         debug(unchanged_indices);
      |         ^~~~~
bridges.cpp:31:20: warning: statement has no effect [-Wunused-value]
   31 | #define debug(...) "zzz"
      |                    ^~~~~
bridges.cpp:128:9: note: in expansion of macro 'debug'
  128 |         debug(process);
      |         ^~~~~
bridges.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int i = 0; i < process.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 35 ms 968 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 19 ms 852 KB Output is correct
6 Correct 15 ms 912 KB Output is correct
7 Correct 18 ms 920 KB Output is correct
8 Correct 17 ms 916 KB Output is correct
9 Correct 16 ms 852 KB Output is correct
10 Correct 19 ms 852 KB Output is correct
11 Correct 17 ms 920 KB Output is correct
12 Correct 19 ms 908 KB Output is correct
13 Correct 24 ms 916 KB Output is correct
14 Correct 23 ms 852 KB Output is correct
15 Correct 18 ms 908 KB Output is correct
16 Correct 17 ms 916 KB Output is correct
17 Correct 19 ms 852 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1387 ms 12416 KB Output is correct
2 Correct 1414 ms 15004 KB Output is correct
3 Correct 1405 ms 14992 KB Output is correct
4 Correct 1381 ms 15160 KB Output is correct
5 Correct 1381 ms 15084 KB Output is correct
6 Correct 1761 ms 15060 KB Output is correct
7 Correct 1767 ms 14988 KB Output is correct
8 Correct 1761 ms 15000 KB Output is correct
9 Correct 39 ms 7372 KB Output is correct
10 Correct 1032 ms 14132 KB Output is correct
11 Correct 1022 ms 13984 KB Output is correct
12 Correct 1160 ms 14704 KB Output is correct
13 Correct 1196 ms 15052 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1057 ms 9792 KB Output is correct
2 Correct 681 ms 8480 KB Output is correct
3 Correct 1165 ms 11924 KB Output is correct
4 Correct 1022 ms 12212 KB Output is correct
5 Correct 38 ms 7372 KB Output is correct
6 Correct 1110 ms 12204 KB Output is correct
7 Correct 984 ms 12104 KB Output is correct
8 Correct 895 ms 12076 KB Output is correct
9 Correct 701 ms 11940 KB Output is correct
10 Correct 670 ms 11964 KB Output is correct
11 Correct 757 ms 12036 KB Output is correct
12 Correct 729 ms 11968 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1657 ms 14976 KB Output is correct
2 Correct 37 ms 5964 KB Output is correct
3 Correct 156 ms 6468 KB Output is correct
4 Correct 74 ms 6576 KB Output is correct
5 Correct 931 ms 15060 KB Output is correct
6 Correct 1625 ms 15020 KB Output is correct
7 Correct 928 ms 14836 KB Output is correct
8 Correct 836 ms 12412 KB Output is correct
9 Correct 818 ms 12256 KB Output is correct
10 Correct 828 ms 12232 KB Output is correct
11 Correct 1267 ms 13536 KB Output is correct
12 Correct 1244 ms 13532 KB Output is correct
13 Correct 1288 ms 13540 KB Output is correct
14 Correct 903 ms 14872 KB Output is correct
15 Correct 886 ms 14968 KB Output is correct
16 Correct 1739 ms 14848 KB Output is correct
17 Correct 1694 ms 14960 KB Output is correct
18 Correct 1709 ms 15012 KB Output is correct
19 Correct 1643 ms 14856 KB Output is correct
20 Correct 1402 ms 13960 KB Output is correct
21 Correct 1410 ms 14308 KB Output is correct
22 Correct 1585 ms 14584 KB Output is correct
23 Correct 986 ms 13792 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1387 ms 12416 KB Output is correct
2 Correct 1414 ms 15004 KB Output is correct
3 Correct 1405 ms 14992 KB Output is correct
4 Correct 1381 ms 15160 KB Output is correct
5 Correct 1381 ms 15084 KB Output is correct
6 Correct 1761 ms 15060 KB Output is correct
7 Correct 1767 ms 14988 KB Output is correct
8 Correct 1761 ms 15000 KB Output is correct
9 Correct 39 ms 7372 KB Output is correct
10 Correct 1032 ms 14132 KB Output is correct
11 Correct 1022 ms 13984 KB Output is correct
12 Correct 1160 ms 14704 KB Output is correct
13 Correct 1196 ms 15052 KB Output is correct
14 Correct 1057 ms 9792 KB Output is correct
15 Correct 681 ms 8480 KB Output is correct
16 Correct 1165 ms 11924 KB Output is correct
17 Correct 1022 ms 12212 KB Output is correct
18 Correct 38 ms 7372 KB Output is correct
19 Correct 1110 ms 12204 KB Output is correct
20 Correct 984 ms 12104 KB Output is correct
21 Correct 895 ms 12076 KB Output is correct
22 Correct 701 ms 11940 KB Output is correct
23 Correct 670 ms 11964 KB Output is correct
24 Correct 757 ms 12036 KB Output is correct
25 Correct 729 ms 11968 KB Output is correct
26 Correct 1376 ms 15084 KB Output is correct
27 Correct 1646 ms 14856 KB Output is correct
28 Correct 1484 ms 15316 KB Output is correct
29 Correct 1204 ms 15000 KB Output is correct
30 Correct 1650 ms 15092 KB Output is correct
31 Correct 1637 ms 14856 KB Output is correct
32 Correct 1653 ms 14908 KB Output is correct
33 Correct 1443 ms 15140 KB Output is correct
34 Correct 1430 ms 15132 KB Output is correct
35 Correct 1452 ms 15296 KB Output is correct
36 Correct 1208 ms 15048 KB Output is correct
37 Correct 1228 ms 15028 KB Output is correct
38 Correct 1208 ms 14956 KB Output is correct
39 Correct 944 ms 15060 KB Output is correct
40 Correct 992 ms 15112 KB Output is correct
41 Correct 952 ms 15028 KB Output is correct
42 Correct 982 ms 14940 KB Output is correct
43 Correct 987 ms 15040 KB Output is correct
44 Correct 974 ms 15092 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 35 ms 968 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 19 ms 852 KB Output is correct
6 Correct 15 ms 912 KB Output is correct
7 Correct 18 ms 920 KB Output is correct
8 Correct 17 ms 916 KB Output is correct
9 Correct 16 ms 852 KB Output is correct
10 Correct 19 ms 852 KB Output is correct
11 Correct 17 ms 920 KB Output is correct
12 Correct 19 ms 908 KB Output is correct
13 Correct 24 ms 916 KB Output is correct
14 Correct 23 ms 852 KB Output is correct
15 Correct 18 ms 908 KB Output is correct
16 Correct 17 ms 916 KB Output is correct
17 Correct 19 ms 852 KB Output is correct
18 Correct 1387 ms 12416 KB Output is correct
19 Correct 1414 ms 15004 KB Output is correct
20 Correct 1405 ms 14992 KB Output is correct
21 Correct 1381 ms 15160 KB Output is correct
22 Correct 1381 ms 15084 KB Output is correct
23 Correct 1761 ms 15060 KB Output is correct
24 Correct 1767 ms 14988 KB Output is correct
25 Correct 1761 ms 15000 KB Output is correct
26 Correct 39 ms 7372 KB Output is correct
27 Correct 1032 ms 14132 KB Output is correct
28 Correct 1022 ms 13984 KB Output is correct
29 Correct 1160 ms 14704 KB Output is correct
30 Correct 1196 ms 15052 KB Output is correct
31 Correct 1057 ms 9792 KB Output is correct
32 Correct 681 ms 8480 KB Output is correct
33 Correct 1165 ms 11924 KB Output is correct
34 Correct 1022 ms 12212 KB Output is correct
35 Correct 38 ms 7372 KB Output is correct
36 Correct 1110 ms 12204 KB Output is correct
37 Correct 984 ms 12104 KB Output is correct
38 Correct 895 ms 12076 KB Output is correct
39 Correct 701 ms 11940 KB Output is correct
40 Correct 670 ms 11964 KB Output is correct
41 Correct 757 ms 12036 KB Output is correct
42 Correct 729 ms 11968 KB Output is correct
43 Correct 1657 ms 14976 KB Output is correct
44 Correct 37 ms 5964 KB Output is correct
45 Correct 156 ms 6468 KB Output is correct
46 Correct 74 ms 6576 KB Output is correct
47 Correct 931 ms 15060 KB Output is correct
48 Correct 1625 ms 15020 KB Output is correct
49 Correct 928 ms 14836 KB Output is correct
50 Correct 836 ms 12412 KB Output is correct
51 Correct 818 ms 12256 KB Output is correct
52 Correct 828 ms 12232 KB Output is correct
53 Correct 1267 ms 13536 KB Output is correct
54 Correct 1244 ms 13532 KB Output is correct
55 Correct 1288 ms 13540 KB Output is correct
56 Correct 903 ms 14872 KB Output is correct
57 Correct 886 ms 14968 KB Output is correct
58 Correct 1739 ms 14848 KB Output is correct
59 Correct 1694 ms 14960 KB Output is correct
60 Correct 1709 ms 15012 KB Output is correct
61 Correct 1643 ms 14856 KB Output is correct
62 Correct 1402 ms 13960 KB Output is correct
63 Correct 1410 ms 14308 KB Output is correct
64 Correct 1585 ms 14584 KB Output is correct
65 Correct 986 ms 13792 KB Output is correct
66 Correct 1376 ms 15084 KB Output is correct
67 Correct 1646 ms 14856 KB Output is correct
68 Correct 1484 ms 15316 KB Output is correct
69 Correct 1204 ms 15000 KB Output is correct
70 Correct 1650 ms 15092 KB Output is correct
71 Correct 1637 ms 14856 KB Output is correct
72 Correct 1653 ms 14908 KB Output is correct
73 Correct 1443 ms 15140 KB Output is correct
74 Correct 1430 ms 15132 KB Output is correct
75 Correct 1452 ms 15296 KB Output is correct
76 Correct 1208 ms 15048 KB Output is correct
77 Correct 1228 ms 15028 KB Output is correct
78 Correct 1208 ms 14956 KB Output is correct
79 Correct 944 ms 15060 KB Output is correct
80 Correct 992 ms 15112 KB Output is correct
81 Correct 952 ms 15028 KB Output is correct
82 Correct 982 ms 14940 KB Output is correct
83 Correct 987 ms 15040 KB Output is correct
84 Correct 974 ms 15092 KB Output is correct
85 Correct 2236 ms 18644 KB Output is correct
86 Correct 199 ms 8348 KB Output is correct
87 Correct 117 ms 8476 KB Output is correct
88 Correct 1381 ms 17108 KB Output is correct
89 Correct 2145 ms 18648 KB Output is correct
90 Correct 1376 ms 17224 KB Output is correct
91 Correct 1474 ms 15092 KB Output is correct
92 Correct 1472 ms 15084 KB Output is correct
93 Correct 1902 ms 14972 KB Output is correct
94 Correct 1914 ms 16940 KB Output is correct
95 Correct 1838 ms 17036 KB Output is correct
96 Correct 2020 ms 16896 KB Output is correct
97 Correct 1065 ms 17144 KB Output is correct
98 Correct 1183 ms 17168 KB Output is correct
99 Correct 2248 ms 18724 KB Output is correct
100 Correct 2256 ms 18548 KB Output is correct
101 Correct 2216 ms 18704 KB Output is correct
102 Correct 2233 ms 18948 KB Output is correct
103 Correct 2199 ms 17472 KB Output is correct
104 Correct 2207 ms 17544 KB Output is correct
105 Correct 1704 ms 17556 KB Output is correct
106 Correct 1421 ms 16932 KB Output is correct
107 Correct 1615 ms 17244 KB Output is correct
108 Correct 2223 ms 18380 KB Output is correct
109 Correct 1565 ms 15908 KB Output is correct