Submission #708438

#	Time	Username	Problem	Language	Result	Execution time	Memory
708438		600Mihnea	Bridges (APIO19_bridges)	C++17	44 / 100	3055 ms	39184 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> initial(m);
	vector<int> what(q);
	vector<vector<int>> intrebari(y);
	const int Magic = 2000;
	int low = 0;
	while (low < q)
	{
		int high = min(q - 1, low + Magic - 1);
		vector<bool> atins(m, 0);
		for (int iq = low; iq <= high; iq++) if (queries[iq][0] == 1) atins[queries[iq][1]] = 1;
		for (int iq = low; iq <= high; iq++) if (queries[iq][0] == 2) intrebari[queries[iq][2]].push_back(iq);
		vector<int> speciale;
		for (int i = 0; i < m; i++) if (atins[i]) speciale.push_back(i);
		for (int i = 0; i < m; i++) initial[i] = edges[i].c;
		Dsu dsu;
		dsu.init(n);
		for (int c = y - 1; c >= 0; c--)
		{
			for (auto& i : cine[c])
			{
				if (edges[i].c == c && !atins[i])
				{
					dsu.join(edges[i].a, edges[i].b);
				}
			}
			for (auto& iq : intrebari[c])
			{
				int init_dim = (int)dsu.histo.size();
				for (auto& i : speciale) edges[i].c = initial[i];
				for (int iq2 = low; iq2 < iq; iq2++)
				{
					auto& query = queries[iq2];
					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;
					}
				}

				int vertex = queries[iq][1], weight = queries[iq][2];
				for (auto& i : speciale)
				{
					if (edges[i].c >= c)
					{
						dsu.join(edges[i].a, edges[i].b);
					}

				}

				what[iq] = dsu.sz[dsu.root(vertex)];
				while ((int)dsu.histo.size() > init_dim) dsu.revert();
			}
		}
		for (int iq = low; iq <= high; 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;
			}
		}
		for (int iq = low; iq <= high; iq++) if (queries[iq][0] == 2) intrebari[queries[iq][2]].clear();
		low = high + 1;
	}
	
	for (int iq = 0; iq < q; iq++)
	{
		if (queries[iq][0] == 2)
		{
			cout << what[iq] << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:216:34: warning: unused variable 'weight' [-Wunused-variable]
  216 |     int vertex = queries[iq][1], weight = queries[iq][2];
      |                                  ^~~~~~

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