oj.uz

답안 #491179

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491179 2021-11-30T16:57:41 Z S2speed 다리 (APIO19_bridges) C++17
100 / 100
 2761 ms 15176 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<ll , pll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

inline ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

int ds[maxn] , dsz[maxn];
vector<int> dv;

int dsu(int v){
	return (ds[v] == v ? v : dsu(ds[v]));
}

void merge(int v , int u){
	v = dsu(v); u = dsu(u);
	if(v == u){
		dv.push_back(-1);
		return;
	}
	if(dsz[v] < dsz[u]) swap(v , u);
	ds[u] = v;
	dsz[v] += dsz[u];
	dv.push_back(u);
	return;
}

void undo(){
	if(dv.back() == -1){
		dv.pop_back();
		return;
	}
	int u = dv.back();
	dsz[ds[u]] -= dsz[u];
	ds[u] = u;
	dv.pop_back();
	return;
}

vector<pii> ed , upd[maxn] , qn , wn;
int w[maxn];
bitset<maxn> mark;
vector<piii> t;
vector<int> en;
int ans[maxn];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n , m;
	cin>>n>>m;
	for(int i = 0 ; i < m ; i++){
		int v , u;
		cin>>v>>u>>w[i]; v--; u--;
		ed.push_back({v , u});
		upd[i].push_back({-1 , w[i]});
	} ed.push_back({0 , 0});
	int q;
	cin>>q;
	for(int i = 0 ; i < q ; i++){
		int y , v , k;
		cin>>y>>v>>k; v--;
		t.push_back({y , {v , k}});
		if(y == 1){
			upd[v].push_back({i , k});
		}
	}
	int sq = min(q , 600);
	for(int e = 0 ; e < q ; e += sq){
		mark.reset();
		en.clear();
		wn.clear();
		qn.clear();
		iota(ds , ds + n , 0);
		fill(dsz , dsz + n , 1);
		dv.clear();
		for(int i = e ; i < min(e + sq , q) ; i++){
			if(t[i].first == 1){
				mark[t[i].second.first] = true;
			} else {
				qn.push_back({t[i].second.second , i});
			}
		}
		for(int i = 0 ; i < m ; i++){
			if(mark[i]){
				en.push_back(i);
				w[i] = upd[i][lower_bound(all(upd[i]) , mp(e + sq , -1)) - upd[i].begin() - 1].second;
			} else {
				wn.push_back({w[i] , i});
			}
		}
		sort(all(wn) , greater<pii>()); wn.push_back({-1 , m});
		sort(all(en));
		sort(all(qn) , greater<pii>()); qn.push_back({-1 , -1});
		int x = 0;
		for(auto p : wn){
			while(true){
				int k = qn[x].first , r = qn[x].second , cnt = 0;
				if(k <= p.first) break;
				for(auto j : en){
					int u = upd[j][lower_bound(all(upd[j]) , mp(r , -1)) - upd[j].begin() - 1].second;
					if(u >= k){
						merge(ed[j].first , ed[j].second);
						cnt++;
					}
				}
				ans[r] = dsz[dsu(t[r].second.first)];
				while(cnt){
					undo(); cnt--;
				}
				x++;
			}
			int j = p.second;
			merge(ed[j].first , ed[j].second);
		}
	}
	for(int i = 0 ; i < q ; i++){
		if(t[i].first == 1) continue;
		cout<<ans[i]<<'\n';
	}
	return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 34 ms 3080 KB Output is correct
4 Correct 4 ms 2956 KB Output is correct
5 Correct 18 ms 3032 KB Output is correct
6 Correct 16 ms 3044 KB Output is correct
7 Correct 17 ms 3048 KB Output is correct
8 Correct 18 ms 3052 KB Output is correct
9 Correct 16 ms 3020 KB Output is correct
10 Correct 18 ms 3020 KB Output is correct
11 Correct 18 ms 3036 KB Output is correct
12 Correct 19 ms 3044 KB Output is correct
13 Correct 27 ms 3044 KB Output is correct
14 Correct 25 ms 3048 KB Output is correct
15 Correct 22 ms 3044 KB Output is correct
16 Correct 21 ms 3176 KB Output is correct
17 Correct 18 ms 3044 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1528 ms 8524 KB Output is correct
2 Correct 1487 ms 8556 KB Output is correct
3 Correct 1509 ms 8512 KB Output is correct
4 Correct 1515 ms 8516 KB Output is correct
5 Correct 1471 ms 8548 KB Output is correct
6 Correct 1747 ms 8724 KB Output is correct
7 Correct 1724 ms 8944 KB Output is correct
8 Correct 1730 ms 8804 KB Output is correct
9 Correct 31 ms 4532 KB Output is correct
10 Correct 1289 ms 8700 KB Output is correct
11 Correct 1328 ms 8532 KB Output is correct
12 Correct 1285 ms 8524 KB Output is correct
13 Correct 1312 ms 9004 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1110 ms 7328 KB Output is correct
2 Correct 677 ms 5628 KB Output is correct
3 Correct 1155 ms 7236 KB Output is correct
4 Correct 1106 ms 7444 KB Output is correct
5 Correct 32 ms 4528 KB Output is correct
6 Correct 1149 ms 7408 KB Output is correct
7 Correct 1043 ms 7368 KB Output is correct
8 Correct 989 ms 7252 KB Output is correct
9 Correct 811 ms 6948 KB Output is correct
10 Correct 781 ms 6848 KB Output is correct
11 Correct 876 ms 7656 KB Output is correct
12 Correct 838 ms 7568 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2242 ms 11472 KB Output is correct
2 Correct 34 ms 4468 KB Output is correct
3 Correct 234 ms 8980 KB Output is correct
4 Correct 152 ms 9016 KB Output is correct
5 Correct 2083 ms 11192 KB Output is correct
6 Correct 2143 ms 11168 KB Output is correct
7 Correct 2160 ms 11176 KB Output is correct
8 Correct 1097 ms 7872 KB Output is correct
9 Correct 1111 ms 7948 KB Output is correct
10 Correct 1101 ms 7964 KB Output is correct
11 Correct 1680 ms 9640 KB Output is correct
12 Correct 1671 ms 9672 KB Output is correct
13 Correct 1711 ms 10156 KB Output is correct
14 Correct 1850 ms 11384 KB Output is correct
15 Correct 2040 ms 11268 KB Output is correct
16 Correct 2228 ms 11116 KB Output is correct
17 Correct 2266 ms 11128 KB Output is correct
18 Correct 2264 ms 11108 KB Output is correct
19 Correct 2206 ms 11224 KB Output is correct
20 Correct 1864 ms 10540 KB Output is correct
21 Correct 1846 ms 10448 KB Output is correct
22 Correct 2152 ms 11012 KB Output is correct
23 Correct 1992 ms 10304 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1528 ms 8524 KB Output is correct
2 Correct 1487 ms 8556 KB Output is correct
3 Correct 1509 ms 8512 KB Output is correct
4 Correct 1515 ms 8516 KB Output is correct
5 Correct 1471 ms 8548 KB Output is correct
6 Correct 1747 ms 8724 KB Output is correct
7 Correct 1724 ms 8944 KB Output is correct
8 Correct 1730 ms 8804 KB Output is correct
9 Correct 31 ms 4532 KB Output is correct
10 Correct 1289 ms 8700 KB Output is correct
11 Correct 1328 ms 8532 KB Output is correct
12 Correct 1285 ms 8524 KB Output is correct
13 Correct 1312 ms 9004 KB Output is correct
14 Correct 1110 ms 7328 KB Output is correct
15 Correct 677 ms 5628 KB Output is correct
16 Correct 1155 ms 7236 KB Output is correct
17 Correct 1106 ms 7444 KB Output is correct
18 Correct 32 ms 4528 KB Output is correct
19 Correct 1149 ms 7408 KB Output is correct
20 Correct 1043 ms 7368 KB Output is correct
21 Correct 989 ms 7252 KB Output is correct
22 Correct 811 ms 6948 KB Output is correct
23 Correct 781 ms 6848 KB Output is correct
24 Correct 876 ms 7656 KB Output is correct
25 Correct 838 ms 7568 KB Output is correct
26 Correct 1515 ms 8524 KB Output is correct
27 Correct 1726 ms 8672 KB Output is correct
28 Correct 1602 ms 8636 KB Output is correct
29 Correct 1398 ms 8500 KB Output is correct
30 Correct 1696 ms 8580 KB Output is correct
31 Correct 1708 ms 8624 KB Output is correct
32 Correct 1690 ms 8592 KB Output is correct
33 Correct 1565 ms 8768 KB Output is correct
34 Correct 1582 ms 8584 KB Output is correct
35 Correct 1588 ms 8800 KB Output is correct
36 Correct 1398 ms 8620 KB Output is correct
37 Correct 1402 ms 8592 KB Output is correct
38 Correct 1376 ms 8516 KB Output is correct
39 Correct 1176 ms 8064 KB Output is correct
40 Correct 1166 ms 8092 KB Output is correct
41 Correct 1189 ms 8344 KB Output is correct
42 Correct 1248 ms 9124 KB Output is correct
43 Correct 1254 ms 8956 KB Output is correct
44 Correct 1243 ms 9096 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 34 ms 3080 KB Output is correct
4 Correct 4 ms 2956 KB Output is correct
5 Correct 18 ms 3032 KB Output is correct
6 Correct 16 ms 3044 KB Output is correct
7 Correct 17 ms 3048 KB Output is correct
8 Correct 18 ms 3052 KB Output is correct
9 Correct 16 ms 3020 KB Output is correct
10 Correct 18 ms 3020 KB Output is correct
11 Correct 18 ms 3036 KB Output is correct
12 Correct 19 ms 3044 KB Output is correct
13 Correct 27 ms 3044 KB Output is correct
14 Correct 25 ms 3048 KB Output is correct
15 Correct 22 ms 3044 KB Output is correct
16 Correct 21 ms 3176 KB Output is correct
17 Correct 18 ms 3044 KB Output is correct
18 Correct 1528 ms 8524 KB Output is correct
19 Correct 1487 ms 8556 KB Output is correct
20 Correct 1509 ms 8512 KB Output is correct
21 Correct 1515 ms 8516 KB Output is correct
22 Correct 1471 ms 8548 KB Output is correct
23 Correct 1747 ms 8724 KB Output is correct
24 Correct 1724 ms 8944 KB Output is correct
25 Correct 1730 ms 8804 KB Output is correct
26 Correct 31 ms 4532 KB Output is correct
27 Correct 1289 ms 8700 KB Output is correct
28 Correct 1328 ms 8532 KB Output is correct
29 Correct 1285 ms 8524 KB Output is correct
30 Correct 1312 ms 9004 KB Output is correct
31 Correct 1110 ms 7328 KB Output is correct
32 Correct 677 ms 5628 KB Output is correct
33 Correct 1155 ms 7236 KB Output is correct
34 Correct 1106 ms 7444 KB Output is correct
35 Correct 32 ms 4528 KB Output is correct
36 Correct 1149 ms 7408 KB Output is correct
37 Correct 1043 ms 7368 KB Output is correct
38 Correct 989 ms 7252 KB Output is correct
39 Correct 811 ms 6948 KB Output is correct
40 Correct 781 ms 6848 KB Output is correct
41 Correct 876 ms 7656 KB Output is correct
42 Correct 838 ms 7568 KB Output is correct
43 Correct 2242 ms 11472 KB Output is correct
44 Correct 34 ms 4468 KB Output is correct
45 Correct 234 ms 8980 KB Output is correct
46 Correct 152 ms 9016 KB Output is correct
47 Correct 2083 ms 11192 KB Output is correct
48 Correct 2143 ms 11168 KB Output is correct
49 Correct 2160 ms 11176 KB Output is correct
50 Correct 1097 ms 7872 KB Output is correct
51 Correct 1111 ms 7948 KB Output is correct
52 Correct 1101 ms 7964 KB Output is correct
53 Correct 1680 ms 9640 KB Output is correct
54 Correct 1671 ms 9672 KB Output is correct
55 Correct 1711 ms 10156 KB Output is correct
56 Correct 1850 ms 11384 KB Output is correct
57 Correct 2040 ms 11268 KB Output is correct
58 Correct 2228 ms 11116 KB Output is correct
59 Correct 2266 ms 11128 KB Output is correct
60 Correct 2264 ms 11108 KB Output is correct
61 Correct 2206 ms 11224 KB Output is correct
62 Correct 1864 ms 10540 KB Output is correct
63 Correct 1846 ms 10448 KB Output is correct
64 Correct 2152 ms 11012 KB Output is correct
65 Correct 1992 ms 10304 KB Output is correct
66 Correct 1515 ms 8524 KB Output is correct
67 Correct 1726 ms 8672 KB Output is correct
68 Correct 1602 ms 8636 KB Output is correct
69 Correct 1398 ms 8500 KB Output is correct
70 Correct 1696 ms 8580 KB Output is correct
71 Correct 1708 ms 8624 KB Output is correct
72 Correct 1690 ms 8592 KB Output is correct
73 Correct 1565 ms 8768 KB Output is correct
74 Correct 1582 ms 8584 KB Output is correct
75 Correct 1588 ms 8800 KB Output is correct
76 Correct 1398 ms 8620 KB Output is correct
77 Correct 1402 ms 8592 KB Output is correct
78 Correct 1376 ms 8516 KB Output is correct
79 Correct 1176 ms 8064 KB Output is correct
80 Correct 1166 ms 8092 KB Output is correct
81 Correct 1189 ms 8344 KB Output is correct
82 Correct 1248 ms 9124 KB Output is correct
83 Correct 1254 ms 8956 KB Output is correct
84 Correct 1243 ms 9096 KB Output is correct
85 Correct 2678 ms 11432 KB Output is correct
86 Correct 259 ms 8972 KB Output is correct
87 Correct 194 ms 9132 KB Output is correct
88 Correct 2516 ms 11336 KB Output is correct
89 Correct 2652 ms 11360 KB Output is correct
90 Correct 2576 ms 11656 KB Output is correct
91 Correct 1612 ms 8696 KB Output is correct
92 Correct 1615 ms 8416 KB Output is correct
93 Correct 1992 ms 8536 KB Output is correct
94 Correct 2196 ms 10128 KB Output is correct
95 Correct 2159 ms 10036 KB Output is correct
96 Correct 2268 ms 10404 KB Output is correct
97 Correct 2248 ms 11308 KB Output is correct
98 Correct 2396 ms 11952 KB Output is correct
99 Correct 2685 ms 11304 KB Output is correct
100 Correct 2761 ms 15176 KB Output is correct
101 Correct 2707 ms 15176 KB Output is correct
102 Correct 2718 ms 15172 KB Output is correct
103 Correct 2542 ms 14016 KB Output is correct
104 Correct 2591 ms 14044 KB Output is correct
105 Correct 2179 ms 14588 KB Output is correct
106 Correct 1829 ms 13948 KB Output is correct
107 Correct 2049 ms 13896 KB Output is correct
108 Correct 2593 ms 14952 KB Output is correct
109 Correct 2411 ms 12644 KB Output is correct