Submission #708426

#	Time	Username	Problem	Language	Result	Execution time	Memory
708426		600Mihnea	Bridges (APIO19_bridges)	C++17	13 / 100	3063 ms	30656 KiB

bridges

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

struct Info
{
	int a, sza, ha;
	int b, szb, hb;
};

struct Dsu
{
	int n;
	vector<int> t, sz, h;
	vector<Info> histo;

	void init(int nn)
	{
		histo.clear();
		t.clear();
		h.clear();
		sz.clear();
		n = nn;
		t.resize(n);
		iota(t.begin(), t.end(), 0);
		sz.resize(n, 1);
		h.resize(n, 0);
	}

	int root(int a)
	{
		assert(0 <= a && a < n);
		while (a != t[a]) a = t[a];
		return a;
	}

	bool join(int a, int b)
	{
		assert(0 <= a && a < n);
		assert(0 <= b && b < n);
		a = root(a);
		b = root(b);
		histo.push_back({ a, sz[a], h[a], b, sz[b], h[b] });
		if (a == b) return 0;
		if (h[a] < h[b]) swap(a, b);
		assert(h[a] >= h[b]);
		t[b] = a;
		h[a] += (h[a] == h[b]);
		sz[a] += sz[b];
		return 1;
	}

	void revert()
	{
		assert(!histo.empty());
		Info info = histo.back();
		histo.pop_back();
		int a = info.a, sza = info.sza, ha = info.ha;
		int b = info.b, szb = info.szb, hb = info.hb;
		t[a] = a;
		sz[a] = sza;
		h[a] = ha;
		t[b] = b;
		sz[b] = szb;
		h[b] = hb;
	}
};

struct Edge
{
	int a, b, c;
};


signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	int n, m, q;
	cin >> n >> m;
	map<int, int> mp;
	vector<Edge> edges(m);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		edges[i] = { a, b, c };
		mp[c] = 0;
	}
	cin >> q;
	vector<vector<int>> queries(q);
	for (auto& query : queries)
	{
		int type;
		cin >> type;
		assert(type == 1 || type == 2);
		if (type == 1)
		{
			int id, nwc;
			cin >> id >> nwc;
			id--;
			assert(0 <= id && id < m);
			query = { type, id, nwc };
			mp[nwc] = 0;
		}
		else
		{
			assert(type == 2);
			int vertex, weight;
			cin >> vertex >> weight;
			vertex--;
			assert(0 <= vertex && vertex < n);
			query = { 2, vertex, weight };
			mp[weight] = 0;
		}
	}
	int y = 0;
	for (auto& it : mp)
	{
		it.second = y++;
	}
	for (int i = 0; i < m; i++)
	{
		edges[i].c = mp[edges[i].c];
	}
	for (auto& query : queries)
	{
		query[2] = mp[query[2]];
	}
	vector<vector<int>> cine(y);
	for (int i = 0; i < m; i++)
	{
		cine[edges[i].c].push_back(i);
	}
	for (auto& query : queries)
	{
		int type = query[0];
		if (type == 1)
		{
			int id = query[1], nwc = query[2];
			cine[nwc].push_back(id);
		}
	}
	vector<int> what(q);
	for (int iq = 0; iq < q; iq++)
	{
		auto& query = queries[iq];
		int type = query[0];
		assert(type == 1 || type == 2);
		if (type == 1)
		{
			int id = query[1], nwc = query[2];
			assert(0 <= id && id < m);
			edges[id].c = nwc;
		}
		else
		{
			assert(type == 2);
			Dsu dsu;
			dsu.init(n);
			int vertex = query[1], weight = query[2];
			for (int c = y - 1; c >= weight; c--)
			{
				for (auto& i : cine[c])
				{
					if (edges[i].c == c)
					{
						dsu.join(edges[i].a, edges[i].b);
					}
				}
			}
			what[iq] = dsu.sz[dsu.root(vertex)];
		}
	}
	for (int iq = 0; iq < q; iq++)
	{
		if (queries[iq][0] == 2)
		{
			cout << what[iq] << "\n";
		}
	}
	return 0;
}

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