Submission #708460

#	Time	Username	Problem	Language	Result	Execution time	Memory
708460		600Mihnea	Bridges (APIO19_bridges)	C++17	100 / 100	2374 ms	25080 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 <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)
	{
		while (a != t[a]) a = t[a];
		return a;
	}

	bool join(int a, int b)
	{
		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);
		t[b] = a;
		h[a] += (h[a] == h[b]);
		sz[a] += sz[b];
		return 1;
	}

	void revert()
	{
		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;
};

struct Q
{
	int x0, x1, x2;
};


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<Q> queries(q);
	for (auto& query : queries)
	{
		int type;
		cin >> type;
		if (type == 1)
		{
			int id, nwc;
			cin >> id >> nwc;
			id--;
			query = { type, id, nwc };
		//	mp[nwc] = 0;
		}
		else
		{
			int vertex, weight;
			cin >> vertex >> weight;
			vertex--;
			query = { 2, vertex, weight };
			mp[weight] = 0;
		}
	}
	int y = 1;
	vector<int> vals;
	vals.push_back(-(int)1e9);
	for (auto& it : mp)
	{
		it.second = y++;
		vals.push_back(it.first);
	}

	auto func = [&](int x)
	{
		int low = 0, high = (int)vals.size() - 1, cnt = 0;
		while (low <= high)
		{
			int mid = (low + high) / 2;
			if (vals[mid] <= x)
			{
				cnt = mid + 1;
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		if (cnt < 1)
		{
			cout << "fail!\n";
			exit(0);
		}
		cnt--;
		return cnt;
	};

	for (auto& query : queries)
	{
		if (query.x0 == 2) query.x2 = mp[query.x2]; else query.x2 = func(query.x2);
	}

	for (int i = 0; i < m; i++)
	{
		edges[i].c = func(edges[i].c);
	}
	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.x0;
		if (type == 1)
		{
			int id = query.x1, nwc = query.x2;
			cine[nwc].push_back(id);
		}
	}
	vector<int> initial(m);
	vector<int> what(q);
	vector<vector<int>> intrebari(y);
	const int Magic = 1000;
	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].x0 == 1) atins[queries[iq].x1] = 1;
		for (int iq = low; iq <= high; iq++) if (queries[iq].x0 == 2) intrebari[queries[iq].x2].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.x0;
					if (type == 1)
					{
						int id = query.x1, nwc = query.x2;
						edges[id].c = nwc;
					}
				}

				int vertex = queries[iq].x1, weight = queries[iq].x2;
				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.x0;
			if (type == 1)
			{
				int id = query.x1, nwc = query.x2;
				edges[id].c = nwc;
			}
		}
		for (int iq = low; iq <= high; iq++) if (queries[iq].x0 == 2) intrebari[queries[iq].x2].clear();
		low = high + 1;
	}

	for (int iq = 0; iq < q; iq++)
	{
		if (queries[iq].x0 == 2)
		{
			cout << what[iq] << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

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

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