답안 #708460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708460	2023-03-11T19:38:51 Z	600Mihnea	다리 (APIO19_bridges)	C++17	100 / 100	2374 ms	25080 KB

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

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.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	50 ms	1280 KB	Output is correct
4	Correct	13 ms	1748 KB	Output is correct
5	Correct	22 ms	1144 KB	Output is correct
6	Correct	18 ms	724 KB	Output is correct
7	Correct	20 ms	620 KB	Output is correct
8	Correct	21 ms	1000 KB	Output is correct
9	Correct	20 ms	468 KB	Output is correct
10	Correct	24 ms	1160 KB	Output is correct
11	Correct	23 ms	1164 KB	Output is correct
12	Correct	23 ms	1108 KB	Output is correct
13	Correct	28 ms	1096 KB	Output is correct
14	Correct	26 ms	1160 KB	Output is correct
15	Correct	24 ms	1188 KB	Output is correct
16	Correct	20 ms	520 KB	Output is correct
17	Correct	20 ms	468 KB	Output is correct

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1394 ms	14040 KB	Output is correct
2	Correct	1387 ms	13868 KB	Output is correct
3	Correct	1457 ms	13812 KB	Output is correct
4	Correct	1396 ms	13644 KB	Output is correct
5	Correct	1478 ms	13664 KB	Output is correct
6	Correct	1385 ms	12784 KB	Output is correct
7	Correct	1372 ms	14104 KB	Output is correct
8	Correct	1402 ms	14776 KB	Output is correct
9	Correct	230 ms	14936 KB	Output is correct
10	Correct	1278 ms	8632 KB	Output is correct
11	Correct	1243 ms	8388 KB	Output is correct
12	Correct	767 ms	15788 KB	Output is correct
13	Correct	1006 ms	14588 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1191 ms	12032 KB	Output is correct
2	Correct	942 ms	6648 KB	Output is correct
3	Correct	1255 ms	9220 KB	Output is correct
4	Correct	1127 ms	11912 KB	Output is correct
5	Correct	171 ms	14896 KB	Output is correct
6	Correct	1293 ms	12852 KB	Output is correct
7	Correct	1092 ms	12616 KB	Output is correct
8	Correct	1004 ms	12660 KB	Output is correct
9	Correct	766 ms	17540 KB	Output is correct
10	Correct	775 ms	17456 KB	Output is correct
11	Correct	694 ms	7580 KB	Output is correct
12	Correct	642 ms	7484 KB	Output is correct

Subtask #4

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1362 ms	24024 KB	Output is correct
2	Correct	239 ms	14996 KB	Output is correct
3	Correct	122 ms	9440 KB	Output is correct
4	Correct	89 ms	7912 KB	Output is correct
5	Correct	740 ms	10384 KB	Output is correct
6	Correct	1427 ms	23884 KB	Output is correct
7	Correct	866 ms	9988 KB	Output is correct
8	Correct	765 ms	19892 KB	Output is correct
9	Correct	745 ms	19960 KB	Output is correct
10	Correct	561 ms	18988 KB	Output is correct
11	Correct	1149 ms	22820 KB	Output is correct
12	Correct	1207 ms	22820 KB	Output is correct
13	Correct	837 ms	22248 KB	Output is correct
14	Correct	830 ms	10592 KB	Output is correct
15	Correct	821 ms	10964 KB	Output is correct
16	Correct	1432 ms	25004 KB	Output is correct
17	Correct	1397 ms	24972 KB	Output is correct
18	Correct	1503 ms	25040 KB	Output is correct
19	Correct	1414 ms	25080 KB	Output is correct
20	Correct	815 ms	22700 KB	Output is correct
21	Correct	807 ms	22464 KB	Output is correct
22	Correct	1098 ms	24320 KB	Output is correct
23	Correct	637 ms	10184 KB	Output is correct

Subtask #5

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1394 ms	14040 KB	Output is correct
2	Correct	1387 ms	13868 KB	Output is correct
3	Correct	1457 ms	13812 KB	Output is correct
4	Correct	1396 ms	13644 KB	Output is correct
5	Correct	1478 ms	13664 KB	Output is correct
6	Correct	1385 ms	12784 KB	Output is correct
7	Correct	1372 ms	14104 KB	Output is correct
8	Correct	1402 ms	14776 KB	Output is correct
9	Correct	230 ms	14936 KB	Output is correct
10	Correct	1278 ms	8632 KB	Output is correct
11	Correct	1243 ms	8388 KB	Output is correct
12	Correct	767 ms	15788 KB	Output is correct
13	Correct	1006 ms	14588 KB	Output is correct
14	Correct	1191 ms	12032 KB	Output is correct
15	Correct	942 ms	6648 KB	Output is correct
16	Correct	1255 ms	9220 KB	Output is correct
17	Correct	1127 ms	11912 KB	Output is correct
18	Correct	171 ms	14896 KB	Output is correct
19	Correct	1293 ms	12852 KB	Output is correct
20	Correct	1092 ms	12616 KB	Output is correct
21	Correct	1004 ms	12660 KB	Output is correct
22	Correct	766 ms	17540 KB	Output is correct
23	Correct	775 ms	17456 KB	Output is correct
24	Correct	694 ms	7580 KB	Output is correct
25	Correct	642 ms	7484 KB	Output is correct
26	Correct	1432 ms	14664 KB	Output is correct
27	Correct	1726 ms	11196 KB	Output is correct
28	Correct	1530 ms	14620 KB	Output is correct
29	Correct	1087 ms	14412 KB	Output is correct
30	Correct	1692 ms	12860 KB	Output is correct
31	Correct	1739 ms	12692 KB	Output is correct
32	Correct	1710 ms	12652 KB	Output is correct
33	Correct	1509 ms	14668 KB	Output is correct
34	Correct	1698 ms	14772 KB	Output is correct
35	Correct	1574 ms	14724 KB	Output is correct
36	Correct	1169 ms	14552 KB	Output is correct
37	Correct	1167 ms	14436 KB	Output is correct
38	Correct	1174 ms	14440 KB	Output is correct
39	Correct	951 ms	19580 KB	Output is correct
40	Correct	972 ms	19552 KB	Output is correct
41	Correct	993 ms	19484 KB	Output is correct
42	Correct	691 ms	9276 KB	Output is correct
43	Correct	704 ms	9308 KB	Output is correct
44	Correct	688 ms	9212 KB	Output is correct

Subtask #6

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	50 ms	1280 KB	Output is correct
4	Correct	13 ms	1748 KB	Output is correct
5	Correct	22 ms	1144 KB	Output is correct
6	Correct	18 ms	724 KB	Output is correct
7	Correct	20 ms	620 KB	Output is correct
8	Correct	21 ms	1000 KB	Output is correct
9	Correct	20 ms	468 KB	Output is correct
10	Correct	24 ms	1160 KB	Output is correct
11	Correct	23 ms	1164 KB	Output is correct
12	Correct	23 ms	1108 KB	Output is correct
13	Correct	28 ms	1096 KB	Output is correct
14	Correct	26 ms	1160 KB	Output is correct
15	Correct	24 ms	1188 KB	Output is correct
16	Correct	20 ms	520 KB	Output is correct
17	Correct	20 ms	468 KB	Output is correct
18	Correct	1394 ms	14040 KB	Output is correct
19	Correct	1387 ms	13868 KB	Output is correct
20	Correct	1457 ms	13812 KB	Output is correct
21	Correct	1396 ms	13644 KB	Output is correct
22	Correct	1478 ms	13664 KB	Output is correct
23	Correct	1385 ms	12784 KB	Output is correct
24	Correct	1372 ms	14104 KB	Output is correct
25	Correct	1402 ms	14776 KB	Output is correct
26	Correct	230 ms	14936 KB	Output is correct
27	Correct	1278 ms	8632 KB	Output is correct
28	Correct	1243 ms	8388 KB	Output is correct
29	Correct	767 ms	15788 KB	Output is correct
30	Correct	1006 ms	14588 KB	Output is correct
31	Correct	1191 ms	12032 KB	Output is correct
32	Correct	942 ms	6648 KB	Output is correct
33	Correct	1255 ms	9220 KB	Output is correct
34	Correct	1127 ms	11912 KB	Output is correct
35	Correct	171 ms	14896 KB	Output is correct
36	Correct	1293 ms	12852 KB	Output is correct
37	Correct	1092 ms	12616 KB	Output is correct
38	Correct	1004 ms	12660 KB	Output is correct
39	Correct	766 ms	17540 KB	Output is correct
40	Correct	775 ms	17456 KB	Output is correct
41	Correct	694 ms	7580 KB	Output is correct
42	Correct	642 ms	7484 KB	Output is correct
43	Correct	1362 ms	24024 KB	Output is correct
44	Correct	239 ms	14996 KB	Output is correct
45	Correct	122 ms	9440 KB	Output is correct
46	Correct	89 ms	7912 KB	Output is correct
47	Correct	740 ms	10384 KB	Output is correct
48	Correct	1427 ms	23884 KB	Output is correct
49	Correct	866 ms	9988 KB	Output is correct
50	Correct	765 ms	19892 KB	Output is correct
51	Correct	745 ms	19960 KB	Output is correct
52	Correct	561 ms	18988 KB	Output is correct
53	Correct	1149 ms	22820 KB	Output is correct
54	Correct	1207 ms	22820 KB	Output is correct
55	Correct	837 ms	22248 KB	Output is correct
56	Correct	830 ms	10592 KB	Output is correct
57	Correct	821 ms	10964 KB	Output is correct
58	Correct	1432 ms	25004 KB	Output is correct
59	Correct	1397 ms	24972 KB	Output is correct
60	Correct	1503 ms	25040 KB	Output is correct
61	Correct	1414 ms	25080 KB	Output is correct
62	Correct	815 ms	22700 KB	Output is correct
63	Correct	807 ms	22464 KB	Output is correct
64	Correct	1098 ms	24320 KB	Output is correct
65	Correct	637 ms	10184 KB	Output is correct
66	Correct	1432 ms	14664 KB	Output is correct
67	Correct	1726 ms	11196 KB	Output is correct
68	Correct	1530 ms	14620 KB	Output is correct
69	Correct	1087 ms	14412 KB	Output is correct
70	Correct	1692 ms	12860 KB	Output is correct
71	Correct	1739 ms	12692 KB	Output is correct
72	Correct	1710 ms	12652 KB	Output is correct
73	Correct	1509 ms	14668 KB	Output is correct
74	Correct	1698 ms	14772 KB	Output is correct
75	Correct	1574 ms	14724 KB	Output is correct
76	Correct	1169 ms	14552 KB	Output is correct
77	Correct	1167 ms	14436 KB	Output is correct
78	Correct	1174 ms	14440 KB	Output is correct
79	Correct	951 ms	19580 KB	Output is correct
80	Correct	972 ms	19552 KB	Output is correct
81	Correct	993 ms	19484 KB	Output is correct
82	Correct	691 ms	9276 KB	Output is correct
83	Correct	704 ms	9308 KB	Output is correct
84	Correct	688 ms	9212 KB	Output is correct
85	Correct	1926 ms	18624 KB	Output is correct
86	Correct	162 ms	10032 KB	Output is correct
87	Correct	144 ms	9036 KB	Output is correct
88	Correct	1406 ms	11752 KB	Output is correct
89	Correct	1979 ms	18460 KB	Output is correct
90	Correct	1506 ms	11076 KB	Output is correct
91	Correct	1659 ms	14468 KB	Output is correct
92	Correct	1714 ms	14340 KB	Output is correct
93	Correct	2177 ms	16488 KB	Output is correct
94	Correct	2013 ms	16980 KB	Output is correct
95	Correct	2003 ms	17100 KB	Output is correct
96	Correct	2066 ms	17312 KB	Output is correct
97	Correct	991 ms	10652 KB	Output is correct
98	Correct	1189 ms	11428 KB	Output is correct
99	Correct	2162 ms	17900 KB	Output is correct
100	Correct	2306 ms	21416 KB	Output is correct
101	Correct	2354 ms	21600 KB	Output is correct
102	Correct	2374 ms	21592 KB	Output is correct
103	Correct	2282 ms	20500 KB	Output is correct
104	Correct	2236 ms	20104 KB	Output is correct
105	Correct	1849 ms	19428 KB	Output is correct
106	Correct	1561 ms	18504 KB	Output is correct
107	Correct	1248 ms	24276 KB	Output is correct
108	Correct	2165 ms	21520 KB	Output is correct
109	Correct	1810 ms	12496 KB	Output is correct