oj.uz

답안 #494667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494667 2021-12-16T01:32:37 Z jjang36524 다리 (APIO19_bridges) C++14
100 / 100
 2830 ms 13304 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define MAX 101010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define B 1000
struct dsu {
	ll p[2][MAX], num[2][MAX];
	ll chk[MAX],chkc;
	ll qnum = 0;
	void init(ll N) {
		ll i;
		chkc = 0;
		for (i = 1; i <= N; i++) p[0][i] = i, num[0][i] = 1, p[1][i] = 0, num[1][i] = 0;
	}
	inline ll find(ll v) 
	{
		while (1)
		{
			ll pp;
			if (!p[qnum][v]) pp = p[0][v];
			else pp = p[qnum][v];
			if (pp == v) return v;
			else {
				v = pp;
			}
		}
		
	}
	inline ll get(ll v)
	{
		if (!num[qnum][v]) return num[0][v];
		else return num[qnum][v];
	}
	void uni(ll a, ll b)
	{
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (get(b) < get(a)) swap(a, b);
		ll x = get(b) + get(a);
		p[qnum][a] = b;
		num[qnum][b] = x;
		if (qnum == 1)
		{
			chk[chkc++] = b;
			chk[chkc++] = a;
		}
	}
	void rb() 
	{
		for (int i=0;i<chkc;i++) 
		{ 
			num[1][chk[i]] = p[1][chk[i]] = 0; 
		}
		chkc = 0;
		qnum = 0;
	}
	void mark() {
		qnum++;
	}
}d;
struct query {
	ll t;
	ll b, r, s, w;
	ll ind;
	query(ll t, ll x, ll y, ll ind) :ind(ind) {
		query::t = t;
		if (t == 1) b = x, r = y;
		else s = x, w = y;
	}
	query() {}
};
pll edge[MAX];
ll val[MAX];
vector<query> qv[2000];
query qarr[MAX];
ll ans[MAX];
ll chk[MAX];
ll nchk[MAX];
bool cmp(query& a, query& b) {
	return a.w > b.w;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, M;
	cin >> N >> M;
	ll i;
	for (i = 1; i <= M; i++) {
		ll a, b;
		cin >> a >> b >> val[i];
		edge[i] = { a, b };
	}
	ll Q;
	cin >> Q;
	for (i = 1; i <= Q; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		qarr[i] = query(a, b, c, i);
		qv[(i - 1) / B].push_back(qarr[i]);
	}
	ll st, en;
	vector<pll> est;
	for (i = 1; i <= M; i++) est.push_back({ -val[i], i });
	for (i = 0; ; i++) {
		st = 1 + i * B;
		en = (1 + i) * B;
		en = min(en, Q);
		if (st > en) break;
		ll j;
		for (j = st; j <= en; j++) if (qarr[j].t == 1) chk[qarr[j].b] = 1;
		vector<query> qq;
		for (auto q : qv[i]) 
			if (q.t == 2) qq.push_back(q);
		if (qq.size()) sort(qq.begin(), qq.end(), cmp);
		vector<pll>::iterator it;
		sort(est.begin(), est.end());
		it = est.begin();
		int vv[1000];
		d.init(N);
		for (ll j = 0; j < qq.size(); j++)
		{
			for (; it != est.end(); it++) {
				if (chk[it->second]) continue;
				if (qq[j].w > -it->first) break;
				else d.uni(edge[it->second].first, edge[it->second].second);
			}
			if (it != est.begin()) it--;
			//dsu c = d;
			d.mark();
			ll cnt = 0;

			int vc = 0;
			int p = qq[j].ind;
			int w = qq[j].w;
			for (ll k = p; k >= st; k--) {
				if (qarr[k].t == 1) {
					if (qarr[k].r >= w && !nchk[qarr[k].b]) {
						d.uni(edge[qarr[k].b].first, edge[qarr[k].b].second);
					}
					nchk[qarr[k].b] = 1;
					vv[vc++] = qarr[k].b;
				}
			}
			for (ll k = en; k > p; k--) {
				if (qarr[k].t == 1) {
					if (!nchk[qarr[k].b] && val[qarr[k].b] >= w) {
						d.uni(edge[qarr[k].b].first, edge[qarr[k].b].second);
						nchk[qarr[k].b] = 1;
						vv[vc++] = qarr[k].b;
					}
				}
			}
			for (ll k = 0; k < vc; k++)
				nchk[vv[k]] = 0;
			ans[qq[j].ind] = d.get(d.find(qq[j].s));
			d.rb();
			//d = c;
		}
		est.clear();
		for (j = st; j <= en; j++) {
			if (qarr[j].t == 1) {
				chk[qarr[j].b] = 0;
				val[qarr[j].b] = qarr[j].r;
			}
		}
		for (j = 1; j <= M; j++)
		{
			est.push_back({ -val[j], j });
		}
	}
	for (i = 1; i <= Q; i++) if (qarr[i].t == 2) cout << ans[i] << ln;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:134:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for (ll j = 0; j < qq.size(); j++)
      |                  ~~^~~~~~~~~~~
bridges.cpp:144:7: warning: unused variable 'cnt' [-Wunused-variable]
  144 |    ll cnt = 0;
      |       ^~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 45 ms 1152 KB Output is correct
4 Correct 10 ms 1048 KB Output is correct
5 Correct 34 ms 1096 KB Output is correct
6 Correct 34 ms 996 KB Output is correct
7 Correct 35 ms 976 KB Output is correct
8 Correct 35 ms 1036 KB Output is correct
9 Correct 34 ms 1020 KB Output is correct
10 Correct 39 ms 1064 KB Output is correct
11 Correct 38 ms 1072 KB Output is correct
12 Correct 38 ms 1056 KB Output is correct
13 Correct 46 ms 1108 KB Output is correct
14 Correct 43 ms 1112 KB Output is correct
15 Correct 42 ms 1100 KB Output is correct
16 Correct 38 ms 1012 KB Output is correct
17 Correct 53 ms 1036 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1472 ms 10636 KB Output is correct
2 Correct 1548 ms 10644 KB Output is correct
3 Correct 1538 ms 10568 KB Output is correct
4 Correct 1720 ms 10732 KB Output is correct
5 Correct 1705 ms 10820 KB Output is correct
6 Correct 2817 ms 10592 KB Output is correct
7 Correct 2764 ms 10912 KB Output is correct
8 Correct 2830 ms 10688 KB Output is correct
9 Correct 78 ms 7076 KB Output is correct
10 Correct 1724 ms 9592 KB Output is correct
11 Correct 1586 ms 9572 KB Output is correct
12 Correct 1324 ms 10992 KB Output is correct
13 Correct 1426 ms 10548 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1361 ms 9576 KB Output is correct
2 Correct 1318 ms 7712 KB Output is correct
3 Correct 1882 ms 9336 KB Output is correct
4 Correct 1476 ms 9568 KB Output is correct
5 Correct 86 ms 7028 KB Output is correct
6 Correct 1670 ms 9468 KB Output is correct
7 Correct 1296 ms 9496 KB Output is correct
8 Correct 1112 ms 9524 KB Output is correct
9 Correct 835 ms 9600 KB Output is correct
10 Correct 769 ms 9568 KB Output is correct
11 Correct 932 ms 9372 KB Output is correct
12 Correct 755 ms 9344 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1604 ms 12556 KB Output is correct
2 Correct 86 ms 7124 KB Output is correct
3 Correct 198 ms 5000 KB Output is correct
4 Correct 144 ms 5136 KB Output is correct
5 Correct 1475 ms 11216 KB Output is correct
6 Correct 1541 ms 12628 KB Output is correct
7 Correct 1436 ms 11100 KB Output is correct
8 Correct 774 ms 10244 KB Output is correct
9 Correct 736 ms 10352 KB Output is correct
10 Correct 780 ms 10352 KB Output is correct
11 Correct 1214 ms 11296 KB Output is correct
12 Correct 1144 ms 11396 KB Output is correct
13 Correct 1111 ms 11452 KB Output is correct
14 Correct 1354 ms 11276 KB Output is correct
15 Correct 1380 ms 11220 KB Output is correct
16 Correct 1539 ms 12532 KB Output is correct
17 Correct 1443 ms 12504 KB Output is correct
18 Correct 1418 ms 12868 KB Output is correct
19 Correct 1433 ms 12632 KB Output is correct
20 Correct 1203 ms 11812 KB Output is correct
21 Correct 1212 ms 11820 KB Output is correct
22 Correct 1346 ms 12548 KB Output is correct
23 Correct 1208 ms 10712 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1472 ms 10636 KB Output is correct
2 Correct 1548 ms 10644 KB Output is correct
3 Correct 1538 ms 10568 KB Output is correct
4 Correct 1720 ms 10732 KB Output is correct
5 Correct 1705 ms 10820 KB Output is correct
6 Correct 2817 ms 10592 KB Output is correct
7 Correct 2764 ms 10912 KB Output is correct
8 Correct 2830 ms 10688 KB Output is correct
9 Correct 78 ms 7076 KB Output is correct
10 Correct 1724 ms 9592 KB Output is correct
11 Correct 1586 ms 9572 KB Output is correct
12 Correct 1324 ms 10992 KB Output is correct
13 Correct 1426 ms 10548 KB Output is correct
14 Correct 1361 ms 9576 KB Output is correct
15 Correct 1318 ms 7712 KB Output is correct
16 Correct 1882 ms 9336 KB Output is correct
17 Correct 1476 ms 9568 KB Output is correct
18 Correct 86 ms 7028 KB Output is correct
19 Correct 1670 ms 9468 KB Output is correct
20 Correct 1296 ms 9496 KB Output is correct
21 Correct 1112 ms 9524 KB Output is correct
22 Correct 835 ms 9600 KB Output is correct
23 Correct 769 ms 9568 KB Output is correct
24 Correct 932 ms 9372 KB Output is correct
25 Correct 755 ms 9344 KB Output is correct
26 Correct 1650 ms 10636 KB Output is correct
27 Correct 2059 ms 10816 KB Output is correct
28 Correct 1638 ms 10824 KB Output is correct
29 Correct 1075 ms 10704 KB Output is correct
30 Correct 1966 ms 10524 KB Output is correct
31 Correct 2086 ms 10828 KB Output is correct
32 Correct 2053 ms 10636 KB Output is correct
33 Correct 1517 ms 10748 KB Output is correct
34 Correct 1621 ms 10736 KB Output is correct
35 Correct 1618 ms 10904 KB Output is correct
36 Correct 1177 ms 10636 KB Output is correct
37 Correct 1170 ms 10532 KB Output is correct
38 Correct 1119 ms 10600 KB Output is correct
39 Correct 841 ms 10700 KB Output is correct
40 Correct 842 ms 10728 KB Output is correct
41 Correct 851 ms 10748 KB Output is correct
42 Correct 842 ms 10520 KB Output is correct
43 Correct 823 ms 10548 KB Output is correct
44 Correct 797 ms 10512 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 45 ms 1152 KB Output is correct
4 Correct 10 ms 1048 KB Output is correct
5 Correct 34 ms 1096 KB Output is correct
6 Correct 34 ms 996 KB Output is correct
7 Correct 35 ms 976 KB Output is correct
8 Correct 35 ms 1036 KB Output is correct
9 Correct 34 ms 1020 KB Output is correct
10 Correct 39 ms 1064 KB Output is correct
11 Correct 38 ms 1072 KB Output is correct
12 Correct 38 ms 1056 KB Output is correct
13 Correct 46 ms 1108 KB Output is correct
14 Correct 43 ms 1112 KB Output is correct
15 Correct 42 ms 1100 KB Output is correct
16 Correct 38 ms 1012 KB Output is correct
17 Correct 53 ms 1036 KB Output is correct
18 Correct 1472 ms 10636 KB Output is correct
19 Correct 1548 ms 10644 KB Output is correct
20 Correct 1538 ms 10568 KB Output is correct
21 Correct 1720 ms 10732 KB Output is correct
22 Correct 1705 ms 10820 KB Output is correct
23 Correct 2817 ms 10592 KB Output is correct
24 Correct 2764 ms 10912 KB Output is correct
25 Correct 2830 ms 10688 KB Output is correct
26 Correct 78 ms 7076 KB Output is correct
27 Correct 1724 ms 9592 KB Output is correct
28 Correct 1586 ms 9572 KB Output is correct
29 Correct 1324 ms 10992 KB Output is correct
30 Correct 1426 ms 10548 KB Output is correct
31 Correct 1361 ms 9576 KB Output is correct
32 Correct 1318 ms 7712 KB Output is correct
33 Correct 1882 ms 9336 KB Output is correct
34 Correct 1476 ms 9568 KB Output is correct
35 Correct 86 ms 7028 KB Output is correct
36 Correct 1670 ms 9468 KB Output is correct
37 Correct 1296 ms 9496 KB Output is correct
38 Correct 1112 ms 9524 KB Output is correct
39 Correct 835 ms 9600 KB Output is correct
40 Correct 769 ms 9568 KB Output is correct
41 Correct 932 ms 9372 KB Output is correct
42 Correct 755 ms 9344 KB Output is correct
43 Correct 1604 ms 12556 KB Output is correct
44 Correct 86 ms 7124 KB Output is correct
45 Correct 198 ms 5000 KB Output is correct
46 Correct 144 ms 5136 KB Output is correct
47 Correct 1475 ms 11216 KB Output is correct
48 Correct 1541 ms 12628 KB Output is correct
49 Correct 1436 ms 11100 KB Output is correct
50 Correct 774 ms 10244 KB Output is correct
51 Correct 736 ms 10352 KB Output is correct
52 Correct 780 ms 10352 KB Output is correct
53 Correct 1214 ms 11296 KB Output is correct
54 Correct 1144 ms 11396 KB Output is correct
55 Correct 1111 ms 11452 KB Output is correct
56 Correct 1354 ms 11276 KB Output is correct
57 Correct 1380 ms 11220 KB Output is correct
58 Correct 1539 ms 12532 KB Output is correct
59 Correct 1443 ms 12504 KB Output is correct
60 Correct 1418 ms 12868 KB Output is correct
61 Correct 1433 ms 12632 KB Output is correct
62 Correct 1203 ms 11812 KB Output is correct
63 Correct 1212 ms 11820 KB Output is correct
64 Correct 1346 ms 12548 KB Output is correct
65 Correct 1208 ms 10712 KB Output is correct
66 Correct 1650 ms 10636 KB Output is correct
67 Correct 2059 ms 10816 KB Output is correct
68 Correct 1638 ms 10824 KB Output is correct
69 Correct 1075 ms 10704 KB Output is correct
70 Correct 1966 ms 10524 KB Output is correct
71 Correct 2086 ms 10828 KB Output is correct
72 Correct 2053 ms 10636 KB Output is correct
73 Correct 1517 ms 10748 KB Output is correct
74 Correct 1621 ms 10736 KB Output is correct
75 Correct 1618 ms 10904 KB Output is correct
76 Correct 1177 ms 10636 KB Output is correct
77 Correct 1170 ms 10532 KB Output is correct
78 Correct 1119 ms 10600 KB Output is correct
79 Correct 841 ms 10700 KB Output is correct
80 Correct 842 ms 10728 KB Output is correct
81 Correct 851 ms 10748 KB Output is correct
82 Correct 842 ms 10520 KB Output is correct
83 Correct 823 ms 10548 KB Output is correct
84 Correct 797 ms 10512 KB Output is correct
85 Correct 2091 ms 13184 KB Output is correct
86 Correct 201 ms 5652 KB Output is correct
87 Correct 190 ms 5996 KB Output is correct
88 Correct 1974 ms 11684 KB Output is correct
89 Correct 2100 ms 13244 KB Output is correct
90 Correct 2061 ms 11300 KB Output is correct
91 Correct 1627 ms 10568 KB Output is correct
92 Correct 1657 ms 10800 KB Output is correct
93 Correct 2717 ms 10916 KB Output is correct
94 Correct 1945 ms 11784 KB Output is correct
95 Correct 2101 ms 12096 KB Output is correct
96 Correct 2590 ms 11680 KB Output is correct
97 Correct 1722 ms 11540 KB Output is correct
98 Correct 1805 ms 11144 KB Output is correct
99 Correct 2286 ms 13304 KB Output is correct
100 Correct 2213 ms 13212 KB Output is correct
101 Correct 2229 ms 13228 KB Output is correct
102 Correct 2181 ms 13152 KB Output is correct
103 Correct 2384 ms 12128 KB Output is correct
104 Correct 2362 ms 11884 KB Output is correct
105 Correct 1594 ms 11964 KB Output is correct
106 Correct 1248 ms 11772 KB Output is correct
107 Correct 1449 ms 12080 KB Output is correct
108 Correct 2203 ms 12556 KB Output is correct
109 Correct 2162 ms 10724 KB Output is correct