oj.uz

답안 #950052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950052 2024-03-20T04:14:55 Z Saul0906 다리 (APIO19_bridges) C++14
100 / 100
 2246 ms 7480 KB 
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define rep2(a,b,c,d) for(int a=b; a<c; a+=d)
#define repa(a, b) for(auto a:b)
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;

struct edge{
	int u, v, w;
	bool operator<(const edge edge2)const{
		return w>edge2.w;
	}
};

struct rback{
	int a, b, c, d;
};

int n, m, q;
const int lim=1e5+5;
edge e[lim], qr[lim];
vector<pii> ewu, qry;
vector<edge> enu;
stack<rback> rbk;
pii dsu[lim];
bool upd[lim];

int find(int u){
	if(dsu[u].fi==u) return u;
	return find(dsu[u].fi);
}

void join(edge a, bool rb){
	int x=find(a.u), y=find(a.v);
	if(x==y) return;
	if(dsu[x].se<dsu[y].se) swap(x,y);
	if(rb) rbk.push({x,dsu[x].se,y,dsu[y].fi});
	dsu[x].se+=dsu[y].se;
	dsu[y].fi=x;
}

void djoin(){
	while(rbk.size()){
		int a=rbk.top().a, b=rbk.top().b, c=rbk.top().c, d=rbk.top().d;
		dsu[a].se=b;
		dsu[c].fi=d;
		rbk.pop();
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	rep(i,1,m+1) cin>>e[i].u>>e[i].v>>e[i].w;
	cin>>q;
	rep(i,0,q) cin>>qr[i].u>>qr[i].v>>qr[i].w;
	vector<pii> ans;
	rep2(i,0,q,500){
		int r=min(i+(int)(500),q), l=0;
		rep(j,1,m+1) upd[j]=false;
		rep(j,i,r){
			if(qr[j].u==1) upd[qr[j].v]=true;
			else qry.pb({qr[j].w,j});
		}
		rep(j,1,m+1){
			if(!upd[j]) enu.pb(e[j]);
			else ewu.pb({j,e[j].w});
		}
		rep(j,1,n+1) dsu[j]={j,1};
		sort(qry.begin(),qry.end());
		reverse(qry.begin(),qry.end());
		sort(enu.begin(),enu.end());
		repa(j,enu){
			while(l<qry.size() && qry[l].fi>j.w){
				repa(k,ewu) e[k.fi].w=k.se;
				rep(k,i,qry[l].se) if(qr[k].u==1) e[qr[k].v].w=qr[k].w;
				repa(k,ewu) if(e[k.fi].w>=qry[l].fi) join(e[k.fi],true);
				ans.pb({qry[l].se,dsu[find(qr[qry[l].se].v)].se});
				//cout<<ans.back().fi<<" "<<ans.back().se<<endl;
				djoin();
				l++;
			}
			//cout<<j.u<<" "<<j.v<<" "<<j.w<<" "<<qry[l].fi<<endl;
			join(j,false);
		}
		while(l<qry.size()){
			repa(k,ewu) e[k.fi].w=k.se;
			rep(k,i,qry[l].se) if(qr[k].u==1) e[qr[k].v].w=qr[k].w;
			repa(k,ewu) if(e[k.fi].w>=qry[l].fi) join(e[k.fi],true);
			ans.pb({qry[l].se,dsu[find(qr[qry[l].se].v)].se});
			djoin();
			l++;
			//cout<<ans.back().fi<<" "<<ans.back().se<<endl;
		}
		rep(k,i,r) if(qr[k].u==1) e[qr[k].v].w=qr[k].w;
		ewu.clear();
		enu.clear();
		qry.clear();
	}
	sort(ans.begin(),ans.end());
	repa(aa,ans) cout<<aa.se<<endl;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:80:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    while(l<qry.size() && qry[l].fi>j.w){
      |          ~^~~~~~~~~~~
bridges.cpp:92:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(l<qry.size()){
      |         ~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 23 ms 2652 KB Output is correct
4 Correct 16 ms 2652 KB Output is correct
5 Correct 15 ms 2396 KB Output is correct
6 Correct 15 ms 2652 KB Output is correct
7 Correct 15 ms 2516 KB Output is correct
8 Correct 15 ms 2512 KB Output is correct
9 Correct 14 ms 2644 KB Output is correct
10 Correct 19 ms 2396 KB Output is correct
11 Correct 15 ms 2540 KB Output is correct
12 Correct 17 ms 2544 KB Output is correct
13 Correct 17 ms 2592 KB Output is correct
14 Correct 16 ms 2652 KB Output is correct
15 Correct 15 ms 2396 KB Output is correct
16 Correct 14 ms 2396 KB Output is correct
17 Correct 14 ms 2588 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1094 ms 4620 KB Output is correct
2 Correct 1142 ms 4616 KB Output is correct
3 Correct 1101 ms 4620 KB Output is correct
4 Correct 1100 ms 4592 KB Output is correct
5 Correct 1112 ms 4644 KB Output is correct
6 Correct 1224 ms 4676 KB Output is correct
7 Correct 1182 ms 5200 KB Output is correct
8 Correct 1234 ms 5036 KB Output is correct
9 Correct 169 ms 3540 KB Output is correct
10 Correct 608 ms 4552 KB Output is correct
11 Correct 617 ms 4808 KB Output is correct
12 Correct 1108 ms 5636 KB Output is correct
13 Correct 957 ms 4020 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 768 ms 3960 KB Output is correct
2 Correct 394 ms 3600 KB Output is correct
3 Correct 772 ms 3940 KB Output is correct
4 Correct 749 ms 4172 KB Output is correct
5 Correct 148 ms 3536 KB Output is correct
6 Correct 771 ms 4168 KB Output is correct
7 Correct 736 ms 4064 KB Output is correct
8 Correct 715 ms 4176 KB Output is correct
9 Correct 699 ms 4492 KB Output is correct
10 Correct 695 ms 4372 KB Output is correct
11 Correct 621 ms 3424 KB Output is correct
12 Correct 593 ms 3600 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2087 ms 7184 KB Output is correct
2 Correct 150 ms 3548 KB Output is correct
3 Correct 215 ms 5208 KB Output is correct
4 Correct 120 ms 5068 KB Output is correct
5 Correct 1192 ms 7288 KB Output is correct
6 Correct 2025 ms 7044 KB Output is correct
7 Correct 1222 ms 7212 KB Output is correct
8 Correct 1014 ms 5388 KB Output is correct
9 Correct 1008 ms 5388 KB Output is correct
10 Correct 1027 ms 5072 KB Output is correct
11 Correct 1566 ms 6160 KB Output is correct
12 Correct 1551 ms 6376 KB Output is correct
13 Correct 1594 ms 6692 KB Output is correct
14 Correct 1180 ms 7376 KB Output is correct
15 Correct 1179 ms 7480 KB Output is correct
16 Correct 2087 ms 7188 KB Output is correct
17 Correct 2134 ms 7028 KB Output is correct
18 Correct 2043 ms 6904 KB Output is correct
19 Correct 2072 ms 7108 KB Output is correct
20 Correct 1733 ms 6580 KB Output is correct
21 Correct 1723 ms 6648 KB Output is correct
22 Correct 2024 ms 7244 KB Output is correct
23 Correct 1276 ms 6844 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1094 ms 4620 KB Output is correct
2 Correct 1142 ms 4616 KB Output is correct
3 Correct 1101 ms 4620 KB Output is correct
4 Correct 1100 ms 4592 KB Output is correct
5 Correct 1112 ms 4644 KB Output is correct
6 Correct 1224 ms 4676 KB Output is correct
7 Correct 1182 ms 5200 KB Output is correct
8 Correct 1234 ms 5036 KB Output is correct
9 Correct 169 ms 3540 KB Output is correct
10 Correct 608 ms 4552 KB Output is correct
11 Correct 617 ms 4808 KB Output is correct
12 Correct 1108 ms 5636 KB Output is correct
13 Correct 957 ms 4020 KB Output is correct
14 Correct 768 ms 3960 KB Output is correct
15 Correct 394 ms 3600 KB Output is correct
16 Correct 772 ms 3940 KB Output is correct
17 Correct 749 ms 4172 KB Output is correct
18 Correct 148 ms 3536 KB Output is correct
19 Correct 771 ms 4168 KB Output is correct
20 Correct 736 ms 4064 KB Output is correct
21 Correct 715 ms 4176 KB Output is correct
22 Correct 699 ms 4492 KB Output is correct
23 Correct 695 ms 4372 KB Output is correct
24 Correct 621 ms 3424 KB Output is correct
25 Correct 593 ms 3600 KB Output is correct
26 Correct 1082 ms 4628 KB Output is correct
27 Correct 1213 ms 4620 KB Output is correct
28 Correct 1143 ms 4536 KB Output is correct
29 Correct 1068 ms 4748 KB Output is correct
30 Correct 1171 ms 4556 KB Output is correct
31 Correct 1164 ms 4660 KB Output is correct
32 Correct 1204 ms 4536 KB Output is correct
33 Correct 1121 ms 4656 KB Output is correct
34 Correct 1167 ms 4552 KB Output is correct
35 Correct 1135 ms 4896 KB Output is correct
36 Correct 1067 ms 4752 KB Output is correct
37 Correct 1087 ms 5080 KB Output is correct
38 Correct 1049 ms 4556 KB Output is correct
39 Correct 1053 ms 5064 KB Output is correct
40 Correct 1028 ms 5316 KB Output is correct
41 Correct 1014 ms 5184 KB Output is correct
42 Correct 906 ms 3764 KB Output is correct
43 Correct 938 ms 4044 KB Output is correct
44 Correct 923 ms 3920 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 23 ms 2652 KB Output is correct
4 Correct 16 ms 2652 KB Output is correct
5 Correct 15 ms 2396 KB Output is correct
6 Correct 15 ms 2652 KB Output is correct
7 Correct 15 ms 2516 KB Output is correct
8 Correct 15 ms 2512 KB Output is correct
9 Correct 14 ms 2644 KB Output is correct
10 Correct 19 ms 2396 KB Output is correct
11 Correct 15 ms 2540 KB Output is correct
12 Correct 17 ms 2544 KB Output is correct
13 Correct 17 ms 2592 KB Output is correct
14 Correct 16 ms 2652 KB Output is correct
15 Correct 15 ms 2396 KB Output is correct
16 Correct 14 ms 2396 KB Output is correct
17 Correct 14 ms 2588 KB Output is correct
18 Correct 1094 ms 4620 KB Output is correct
19 Correct 1142 ms 4616 KB Output is correct
20 Correct 1101 ms 4620 KB Output is correct
21 Correct 1100 ms 4592 KB Output is correct
22 Correct 1112 ms 4644 KB Output is correct
23 Correct 1224 ms 4676 KB Output is correct
24 Correct 1182 ms 5200 KB Output is correct
25 Correct 1234 ms 5036 KB Output is correct
26 Correct 169 ms 3540 KB Output is correct
27 Correct 608 ms 4552 KB Output is correct
28 Correct 617 ms 4808 KB Output is correct
29 Correct 1108 ms 5636 KB Output is correct
30 Correct 957 ms 4020 KB Output is correct
31 Correct 768 ms 3960 KB Output is correct
32 Correct 394 ms 3600 KB Output is correct
33 Correct 772 ms 3940 KB Output is correct
34 Correct 749 ms 4172 KB Output is correct
35 Correct 148 ms 3536 KB Output is correct
36 Correct 771 ms 4168 KB Output is correct
37 Correct 736 ms 4064 KB Output is correct
38 Correct 715 ms 4176 KB Output is correct
39 Correct 699 ms 4492 KB Output is correct
40 Correct 695 ms 4372 KB Output is correct
41 Correct 621 ms 3424 KB Output is correct
42 Correct 593 ms 3600 KB Output is correct
43 Correct 2087 ms 7184 KB Output is correct
44 Correct 150 ms 3548 KB Output is correct
45 Correct 215 ms 5208 KB Output is correct
46 Correct 120 ms 5068 KB Output is correct
47 Correct 1192 ms 7288 KB Output is correct
48 Correct 2025 ms 7044 KB Output is correct
49 Correct 1222 ms 7212 KB Output is correct
50 Correct 1014 ms 5388 KB Output is correct
51 Correct 1008 ms 5388 KB Output is correct
52 Correct 1027 ms 5072 KB Output is correct
53 Correct 1566 ms 6160 KB Output is correct
54 Correct 1551 ms 6376 KB Output is correct
55 Correct 1594 ms 6692 KB Output is correct
56 Correct 1180 ms 7376 KB Output is correct
57 Correct 1179 ms 7480 KB Output is correct
58 Correct 2087 ms 7188 KB Output is correct
59 Correct 2134 ms 7028 KB Output is correct
60 Correct 2043 ms 6904 KB Output is correct
61 Correct 2072 ms 7108 KB Output is correct
62 Correct 1733 ms 6580 KB Output is correct
63 Correct 1723 ms 6648 KB Output is correct
64 Correct 2024 ms 7244 KB Output is correct
65 Correct 1276 ms 6844 KB Output is correct
66 Correct 1082 ms 4628 KB Output is correct
67 Correct 1213 ms 4620 KB Output is correct
68 Correct 1143 ms 4536 KB Output is correct
69 Correct 1068 ms 4748 KB Output is correct
70 Correct 1171 ms 4556 KB Output is correct
71 Correct 1164 ms 4660 KB Output is correct
72 Correct 1204 ms 4536 KB Output is correct
73 Correct 1121 ms 4656 KB Output is correct
74 Correct 1167 ms 4552 KB Output is correct
75 Correct 1135 ms 4896 KB Output is correct
76 Correct 1067 ms 4752 KB Output is correct
77 Correct 1087 ms 5080 KB Output is correct
78 Correct 1049 ms 4556 KB Output is correct
79 Correct 1053 ms 5064 KB Output is correct
80 Correct 1028 ms 5316 KB Output is correct
81 Correct 1014 ms 5184 KB Output is correct
82 Correct 906 ms 3764 KB Output is correct
83 Correct 938 ms 4044 KB Output is correct
84 Correct 923 ms 3920 KB Output is correct
85 Correct 2181 ms 5752 KB Output is correct
86 Correct 217 ms 5068 KB Output is correct
87 Correct 114 ms 5068 KB Output is correct
88 Correct 1263 ms 6160 KB Output is correct
89 Correct 2220 ms 5792 KB Output is correct
90 Correct 1288 ms 5832 KB Output is correct
91 Correct 1141 ms 4796 KB Output is correct
92 Correct 1131 ms 4692 KB Output is correct
93 Correct 1224 ms 4744 KB Output is correct
94 Correct 1727 ms 5156 KB Output is correct
95 Correct 1703 ms 5060 KB Output is correct
96 Correct 1721 ms 5316 KB Output is correct
97 Correct 1284 ms 6964 KB Output is correct
98 Correct 1179 ms 5240 KB Output is correct
99 Correct 2204 ms 5924 KB Output is correct
100 Correct 2204 ms 6264 KB Output is correct
101 Correct 2246 ms 5812 KB Output is correct
102 Correct 2207 ms 6268 KB Output is correct
103 Correct 1886 ms 5612 KB Output is correct
104 Correct 1885 ms 5700 KB Output is correct
105 Correct 1689 ms 4976 KB Output is correct
106 Correct 1477 ms 4868 KB Output is correct
107 Correct 1823 ms 6844 KB Output is correct
108 Correct 2103 ms 6028 KB Output is correct
109 Correct 1310 ms 5576 KB Output is correct