Submission #1084117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084117		QwertyPi	Bridges (APIO19_bridges)	C++14	100 / 100	2156 ms	14320 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

struct edge{
	int u, v, w; bool ban;
    int ow;
};

struct query{
	int t, a, b;
};

const int BLOCK = 600;
const int N = 2.1e5 + 11;

int ans[N]; bool ban[N];
struct DSU{
	int dsu[N], sz[N];
	vector<pair<int, int>> stmp;
	DSU() { iota(dsu, dsu + N, 0), fill(sz, sz + N, 1); }
	int f(int x) { return x == dsu[x] ? x : f(dsu[x]); }
	void g(int x, int y) {
		x = f(x), y = f(y);
		if (x == y) return void(stmp.push_back({-1, -1}));
		if (sz[x] > sz[y]) swap(x, y);
		dsu[x] = y; sz[y] += sz[x];
		stmp.push_back({x, y});
	}
	void rollback() {
		assert(!stmp.empty());
		auto [x, y] = stmp.back(); stmp.pop_back();
		sz[y] -= sz[x]; dsu[x] = x;
	}
    void reset() {
        while (!stmp.empty()) {
            rollback();
        }
    }
} dsu;

int main() {
	fill(ans, ans + N, -1);
	cin.tie(0)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	vector<edge> E;
    E.push_back({});
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		E.push_back({u, v, w});
	}

	int q; cin >> q;
	vector<query> Q;
    for (int i = 1; i <= m; i++) {
        Q.push_back({1, i, E[i].w});
    }
	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		int a, b; cin >> a >> b;
		Q.push_back({t, a, b});
	}

	while (Q.size() % BLOCK != 0) {
		Q.push_back({1, 0, 0});
	}

	assert(E.size() == m + 1);
	
    vector<int> e(E.size()); iota(e.begin(), e.end(), 1);
	for (int i = 0; i < Q.size(); i += BLOCK) {
        sort(e.begin(), e.end(), [&](auto x, auto y){
            return E[x].w > E[y].w;
        });
        
		set<int> edges;
		auto upd_edge = [&] (int from, int to, bool state) {
//             cout << "UPD_EDGE" << ' ' << from << ' ' << to << ' ' << state << endl;
			for (int j = from; j < to; j++) {
				auto [t, a, b] = Q[j];
				if (t == 1) {
//                     cout << "GOT " << a << endl;
					ban[a] = state;
                    if (a) edges.insert(a);
				}
			}
		};
        
//         cout << edges.size() << endl;

		upd_edge(i, i + BLOCK, true);
        vector<int> to_check(edges.begin(), edges.end());
        
		vector<query> C;
		for (int j = i; j < i + BLOCK; j++) {
			auto [t, a, b] = Q[j];
			if (t == 2) {
				C.push_back({j, a, b});
			}
		}
		sort(C.begin(), C.end(), [] (auto x, auto y) {
            return x.b > y.b;
        });
        
        int ei = 0;
        for (auto [id, s, w] : C) {
//             cout << "C: " << id << ' ' << s << ' ' << w << endl;
            while (ei < E.size() && E[e[ei]].w >= w) {
                if (!ban[e[ei]]) {
//                     cout << "TIME ADD EDGE " << E[e[ei]].u << ' ' << E[e[ei]].v << endl;
                    dsu.g(E[e[ei]].u, E[e[ei]].v);
                }
                ++ei;
            }
            int cnt = 0;
            for (int j = id - 1; j >= i; j--) {
                auto [t, a, b] = Q[j];
//                 cout << a << " => " << E[a].ow << endl;
                if (t == 1 && E[a].ow == 0) {
                    E[a].ow = E[a].w, E[a].w = b;
                    if (E[a].w >= w) {
//                         cout << "ADD EDGE " << E[a].u << ' ' << E[a].v << endl;
                        dsu.g(E[a].u, E[a].v), ++cnt;
                    }
                }
            }
//             cout << "TO CHECK" << endl;
//             for (auto x : to_check) {
//                 cout << x << ' ';
//             }
//             cout << endl;
            for (auto x : to_check) {
                if (E[x].ow == 0 && E[x].w >= w) {
//                     cout << "ADD EDGE " << E[x].u << ' ' << E[x].v << endl;
                    dsu.g(E[x].u, E[x].v), ++cnt;
                }
            }
//             cout << "QUERY" << endl;
            ans[id] = dsu.sz[dsu.f(s)];
            for (int j = 0; j < cnt; j++) dsu.rollback();
            for (auto x : to_check) {
                if (E[x].ow) {
                    E[x].w = E[x].ow;
                    E[x].ow = 0;
                }
            }
        }
        
		upd_edge(i, i + BLOCK, false);

		for (int j = i; j < i + BLOCK; j++) {
			auto [t, a, b] = Q[j];
			if (t == 1) {
				E[a].w = b;
			}
		}
//         for (auto [x, y, w, a, b] : E) {
//             cout << x << " <=> " << y << ": " << w << " | ";
//         }
//         cout << endl;
        
        dsu.reset();
	}

	for (int i = 0; i < Q.size(); i++) {
		if (Q[i].t == 2) {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::rollback()':
bridges.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   auto [x, y] = stmp.back(); stmp.pop_back();
      |        ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from bridges.cpp:1:
bridges.cpp: In function 'int main()':
bridges.cpp:67:18: warning: comparison of integer expressions of different signedness: 'std::vector<edge>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |  assert(E.size() == m + 1);
      |         ~~~~~~~~~^~~~~~~~
bridges.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (int i = 0; i < Q.size(); i += BLOCK) {
      |                  ~~^~~~~~~~~~
bridges.cpp: In lambda function:
bridges.cpp:79:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     auto [t, a, b] = Q[j];
      |          ^
bridges.cpp: In function 'int main()':
bridges.cpp:95:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |    auto [t, a, b] = Q[j];
      |         ^
bridges.cpp:105:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |         for (auto [id, s, w] : C) {
      |                   ^
bridges.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             while (ei < E.size() && E[e[ei]].w >= w) {
      |                    ~~~^~~~~~~~~~
bridges.cpp:116:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |                 auto [t, a, b] = Q[j];
      |                      ^
bridges.cpp:151:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |    auto [t, a, b] = Q[j];
      |         ^
bridges.cpp:164:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |  for (int i = 0; i < Q.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27