oj.uz

답안 #889105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889105 2023-12-18T21:43:33 Z BBart888 다리 (APIO19_bridges) C++14
100 / 100
 1542 ms 72480 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN= 1e6 + 111;

using  ll = long long;

int sz[MAXN];
int par[MAXN];
stack<int> stk;
const int B = 1000;
int n;
void reset()
{
	for(int i =1;i<=n;i++)
	{	par[i] = i;
		sz[i] =1;
	
}
}


int find(int a)
{
	while(par[a] != a)
		a = par[a];
	return a;
}


void onion(int a,int b)
{
	a = find(a);
	b = find(b);
	
	if(a == b)
		return;
	if(sz[a] > sz[b])	
		swap(a,b);
	sz[b]+=sz[a];
	par[a] = par[b];
	stk.push(a);
}


void roll_back(int x)
{
	while((int)stk.size() > x)
	{
		int k =stk.top();
		stk.pop();
		sz[find(k)] -= sz[k];
		par[k] = k;
	}
}

int m;
int u[MAXN];
int v[MAXN];
int w[MAXN];
int t[MAXN];
int x[MAXN];
int y[MAXN];
bool changed[MAXN];
vector<int> to_join[MAXN];
int ans[MAXN];
int q;


int main()
{
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	for(int i =1;i<=m;i++)
		cin>>u[i]>>v[i]>>w[i];
	
	cin>>q;
	
	for(int i =1;i<=q;i++)
		cin>>t[i]>>x[i]>>y[i];
		
	for(int l =1;l<=q;l+=B)
	{
		int r = min(l+B-1,q);
		reset();
		
		fill(changed+1,changed+m+1,false);

		vector<int> ask,upd,unchanged;
		
		for(int i = l;i<=r;i++)
		{
			if(t[i] == 1)
			{
				changed[x[i]] = true;
				upd.push_back(i);
			}
			else
				ask.push_back(i);
		}
		
		for(int i =1;i<=m;i++)
			if(!changed[i])
				unchanged.push_back(i);
		
		for(int i = l;i<=r;i++)
		{
			if(t[i] == 1)
				w[x[i]] = y[i];
			else
			{
				to_join[i-l].clear();
				for(int j : upd)
					if(w[x[j]] >= y[i])
						to_join[i-l].push_back(x[j]);
			}
		}
		
		sort(ask.begin(),ask.end(),[&](int a,int b){return y[a] > y[b];});
		sort(unchanged.begin(),unchanged.end(),[&](int a,int b){return w[a] > w[b];});
		
		int ptr =0;
		
		for(int i : ask)
		{
			while(ptr < (int)unchanged.size() && y[i] <= w[unchanged[ptr]])
				{
					
					onion(u[unchanged[ptr]],v[unchanged[ptr]]);
					ptr++;
				}
			
			int prv_size = stk.size();
			for(int j : to_join[i-l])
				onion(u[j],v[j]);
			//cout<<find(x[i])<<" "<<'\n';
			ans[i]= sz[find(x[i])];
			//cout<<"ge\n";	
			roll_back(prv_size);
		}
	}

	

	for(int i = 1;i<=q;i++)
		if(t[i] == 2)
			cout<<ans[i]<<"\n";
	
	
	
	return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 41304 KB Output is correct
2 Correct 7 ms 41308 KB Output is correct
3 Correct 35 ms 43568 KB Output is correct
4 Correct 13 ms 35524 KB Output is correct
5 Correct 34 ms 43868 KB Output is correct
6 Correct 27 ms 43612 KB Output is correct
7 Correct 29 ms 44580 KB Output is correct
8 Correct 37 ms 43684 KB Output is correct
9 Correct 32 ms 45148 KB Output is correct
10 Correct 38 ms 43752 KB Output is correct
11 Correct 38 ms 43600 KB Output is correct
12 Correct 41 ms 43856 KB Output is correct
13 Correct 46 ms 44128 KB Output is correct
14 Correct 39 ms 43612 KB Output is correct
15 Correct 42 ms 43768 KB Output is correct
16 Correct 32 ms 44876 KB Output is correct
17 Correct 33 ms 44368 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 862 ms 66680 KB Output is correct
2 Correct 875 ms 69676 KB Output is correct
3 Correct 886 ms 69632 KB Output is correct
4 Correct 891 ms 69456 KB Output is correct
5 Correct 888 ms 69676 KB Output is correct
6 Correct 995 ms 71324 KB Output is correct
7 Correct 1031 ms 71144 KB Output is correct
8 Correct 993 ms 70992 KB Output is correct
9 Correct 65 ms 38992 KB Output is correct
10 Correct 534 ms 70308 KB Output is correct
11 Correct 501 ms 70168 KB Output is correct
12 Correct 734 ms 67848 KB Output is correct
13 Correct 732 ms 70900 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 681 ms 59556 KB Output is correct
2 Correct 439 ms 52664 KB Output is correct
3 Correct 702 ms 63556 KB Output is correct
4 Correct 650 ms 62040 KB Output is correct
5 Correct 66 ms 38996 KB Output is correct
6 Correct 699 ms 62016 KB Output is correct
7 Correct 658 ms 61812 KB Output is correct
8 Correct 587 ms 61692 KB Output is correct
9 Correct 505 ms 60480 KB Output is correct
10 Correct 474 ms 60188 KB Output is correct
11 Correct 516 ms 63292 KB Output is correct
12 Correct 508 ms 63328 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1239 ms 64908 KB Output is correct
2 Correct 62 ms 37720 KB Output is correct
3 Correct 172 ms 42644 KB Output is correct
4 Correct 102 ms 42412 KB Output is correct
5 Correct 617 ms 64960 KB Output is correct
6 Correct 1209 ms 64812 KB Output is correct
7 Correct 605 ms 65076 KB Output is correct
8 Correct 591 ms 64548 KB Output is correct
9 Correct 604 ms 64676 KB Output is correct
10 Correct 592 ms 64788 KB Output is correct
11 Correct 921 ms 65432 KB Output is correct
12 Correct 897 ms 65228 KB Output is correct
13 Correct 928 ms 65300 KB Output is correct
14 Correct 561 ms 65028 KB Output is correct
15 Correct 590 ms 65372 KB Output is correct
16 Correct 1224 ms 65088 KB Output is correct
17 Correct 1235 ms 65312 KB Output is correct
18 Correct 1251 ms 65388 KB Output is correct
19 Correct 1226 ms 65336 KB Output is correct
20 Correct 1032 ms 65364 KB Output is correct
21 Correct 1064 ms 65488 KB Output is correct
22 Correct 1169 ms 65096 KB Output is correct
23 Correct 681 ms 63476 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 862 ms 66680 KB Output is correct
2 Correct 875 ms 69676 KB Output is correct
3 Correct 886 ms 69632 KB Output is correct
4 Correct 891 ms 69456 KB Output is correct
5 Correct 888 ms 69676 KB Output is correct
6 Correct 995 ms 71324 KB Output is correct
7 Correct 1031 ms 71144 KB Output is correct
8 Correct 993 ms 70992 KB Output is correct
9 Correct 65 ms 38992 KB Output is correct
10 Correct 534 ms 70308 KB Output is correct
11 Correct 501 ms 70168 KB Output is correct
12 Correct 734 ms 67848 KB Output is correct
13 Correct 732 ms 70900 KB Output is correct
14 Correct 681 ms 59556 KB Output is correct
15 Correct 439 ms 52664 KB Output is correct
16 Correct 702 ms 63556 KB Output is correct
17 Correct 650 ms 62040 KB Output is correct
18 Correct 66 ms 38996 KB Output is correct
19 Correct 699 ms 62016 KB Output is correct
20 Correct 658 ms 61812 KB Output is correct
21 Correct 587 ms 61692 KB Output is correct
22 Correct 505 ms 60480 KB Output is correct
23 Correct 474 ms 60188 KB Output is correct
24 Correct 516 ms 63292 KB Output is correct
25 Correct 508 ms 63328 KB Output is correct
26 Correct 909 ms 69668 KB Output is correct
27 Correct 976 ms 71052 KB Output is correct
28 Correct 903 ms 69672 KB Output is correct
29 Correct 744 ms 69208 KB Output is correct
30 Correct 958 ms 71400 KB Output is correct
31 Correct 948 ms 71344 KB Output is correct
32 Correct 981 ms 71468 KB Output is correct
33 Correct 888 ms 69464 KB Output is correct
34 Correct 935 ms 69572 KB Output is correct
35 Correct 887 ms 69408 KB Output is correct
36 Correct 761 ms 69148 KB Output is correct
37 Correct 771 ms 69280 KB Output is correct
38 Correct 741 ms 69300 KB Output is correct
39 Correct 664 ms 67860 KB Output is correct
40 Correct 662 ms 67988 KB Output is correct
41 Correct 668 ms 67748 KB Output is correct
42 Correct 648 ms 69688 KB Output is correct
43 Correct 644 ms 69676 KB Output is correct
44 Correct 659 ms 69476 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 41304 KB Output is correct
2 Correct 7 ms 41308 KB Output is correct
3 Correct 35 ms 43568 KB Output is correct
4 Correct 13 ms 35524 KB Output is correct
5 Correct 34 ms 43868 KB Output is correct
6 Correct 27 ms 43612 KB Output is correct
7 Correct 29 ms 44580 KB Output is correct
8 Correct 37 ms 43684 KB Output is correct
9 Correct 32 ms 45148 KB Output is correct
10 Correct 38 ms 43752 KB Output is correct
11 Correct 38 ms 43600 KB Output is correct
12 Correct 41 ms 43856 KB Output is correct
13 Correct 46 ms 44128 KB Output is correct
14 Correct 39 ms 43612 KB Output is correct
15 Correct 42 ms 43768 KB Output is correct
16 Correct 32 ms 44876 KB Output is correct
17 Correct 33 ms 44368 KB Output is correct
18 Correct 862 ms 66680 KB Output is correct
19 Correct 875 ms 69676 KB Output is correct
20 Correct 886 ms 69632 KB Output is correct
21 Correct 891 ms 69456 KB Output is correct
22 Correct 888 ms 69676 KB Output is correct
23 Correct 995 ms 71324 KB Output is correct
24 Correct 1031 ms 71144 KB Output is correct
25 Correct 993 ms 70992 KB Output is correct
26 Correct 65 ms 38992 KB Output is correct
27 Correct 534 ms 70308 KB Output is correct
28 Correct 501 ms 70168 KB Output is correct
29 Correct 734 ms 67848 KB Output is correct
30 Correct 732 ms 70900 KB Output is correct
31 Correct 681 ms 59556 KB Output is correct
32 Correct 439 ms 52664 KB Output is correct
33 Correct 702 ms 63556 KB Output is correct
34 Correct 650 ms 62040 KB Output is correct
35 Correct 66 ms 38996 KB Output is correct
36 Correct 699 ms 62016 KB Output is correct
37 Correct 658 ms 61812 KB Output is correct
38 Correct 587 ms 61692 KB Output is correct
39 Correct 505 ms 60480 KB Output is correct
40 Correct 474 ms 60188 KB Output is correct
41 Correct 516 ms 63292 KB Output is correct
42 Correct 508 ms 63328 KB Output is correct
43 Correct 1239 ms 64908 KB Output is correct
44 Correct 62 ms 37720 KB Output is correct
45 Correct 172 ms 42644 KB Output is correct
46 Correct 102 ms 42412 KB Output is correct
47 Correct 617 ms 64960 KB Output is correct
48 Correct 1209 ms 64812 KB Output is correct
49 Correct 605 ms 65076 KB Output is correct
50 Correct 591 ms 64548 KB Output is correct
51 Correct 604 ms 64676 KB Output is correct
52 Correct 592 ms 64788 KB Output is correct
53 Correct 921 ms 65432 KB Output is correct
54 Correct 897 ms 65228 KB Output is correct
55 Correct 928 ms 65300 KB Output is correct
56 Correct 561 ms 65028 KB Output is correct
57 Correct 590 ms 65372 KB Output is correct
58 Correct 1224 ms 65088 KB Output is correct
59 Correct 1235 ms 65312 KB Output is correct
60 Correct 1251 ms 65388 KB Output is correct
61 Correct 1226 ms 65336 KB Output is correct
62 Correct 1032 ms 65364 KB Output is correct
63 Correct 1064 ms 65488 KB Output is correct
64 Correct 1169 ms 65096 KB Output is correct
65 Correct 681 ms 63476 KB Output is correct
66 Correct 909 ms 69668 KB Output is correct
67 Correct 976 ms 71052 KB Output is correct
68 Correct 903 ms 69672 KB Output is correct
69 Correct 744 ms 69208 KB Output is correct
70 Correct 958 ms 71400 KB Output is correct
71 Correct 948 ms 71344 KB Output is correct
72 Correct 981 ms 71468 KB Output is correct
73 Correct 888 ms 69464 KB Output is correct
74 Correct 935 ms 69572 KB Output is correct
75 Correct 887 ms 69408 KB Output is correct
76 Correct 761 ms 69148 KB Output is correct
77 Correct 771 ms 69280 KB Output is correct
78 Correct 741 ms 69300 KB Output is correct
79 Correct 664 ms 67860 KB Output is correct
80 Correct 662 ms 67988 KB Output is correct
81 Correct 668 ms 67748 KB Output is correct
82 Correct 648 ms 69688 KB Output is correct
83 Correct 644 ms 69676 KB Output is correct
84 Correct 659 ms 69476 KB Output is correct
85 Correct 1501 ms 70908 KB Output is correct
86 Correct 185 ms 46308 KB Output is correct
87 Correct 124 ms 47512 KB Output is correct
88 Correct 833 ms 71408 KB Output is correct
89 Correct 1462 ms 71220 KB Output is correct
90 Correct 812 ms 71208 KB Output is correct
91 Correct 917 ms 69588 KB Output is correct
92 Correct 915 ms 69668 KB Output is correct
93 Correct 1047 ms 70944 KB Output is correct
94 Correct 1202 ms 70796 KB Output is correct
95 Correct 1249 ms 70936 KB Output is correct
96 Correct 1199 ms 72352 KB Output is correct
97 Correct 719 ms 67816 KB Output is correct
98 Correct 712 ms 70888 KB Output is correct
99 Correct 1484 ms 71580 KB Output is correct
100 Correct 1497 ms 71100 KB Output is correct
101 Correct 1542 ms 71352 KB Output is correct
102 Correct 1465 ms 71360 KB Output is correct
103 Correct 1342 ms 72364 KB Output is correct
104 Correct 1323 ms 72480 KB Output is correct
105 Correct 1161 ms 72180 KB Output is correct
106 Correct 980 ms 71876 KB Output is correct
107 Correct 1117 ms 68976 KB Output is correct
108 Correct 1394 ms 71508 KB Output is correct
109 Correct 916 ms 69192 KB Output is correct