oj.uz

Submission #208192

# Submission time Handle Problem Language Result Execution time Memory
208192 2020-03-10T08:31:04 Z Segtree Bridges (APIO19_bridges) C++14
100 / 100
 2937 ms 16472 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define B 800
#define N 50010
#define M 100010
namespace uf{
	ll dat[N];
	stack<P> s;
	void init(){
		rep(i,N)dat[i]=-1;
		while(!s.empty())s.pop();
	}
	void confirm(){
		while(!s.empty())s.pop();
	}
	ll find(ll x){
		return (dat[x]<0?x:find(dat[x]));
	}
	ll siz(ll x){
		return -dat[find(x)];
	}
	void unite(ll a,ll b){
		a=find(a),b=find(b);
		if(a==b)return;
		if(-dat[a]<-dat[b])swap(a,b);
		s.push(make_pair(a,dat[a]));
		s.push(make_pair(b,dat[b]));
		dat[a]+=dat[b];
		dat[b]=a;
	}
	void rollback(){
		while(!s.empty()){
			dat[s.top().first]=s.top().second;
			s.pop();
		}
	}
};
typedef struct qry{
	ll s,w,id;
	bool operator<(const qry&key)const{
		return this->w>key.w;
	}
}qry;//t=2のクエリの構造体
int n,m,q;
int a[M],b[M],c[M];
int t[M],x[M],y[M];
int fans[M];
ll cc[B+1][B];
bool used[N];

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	cin>>q;
	rep(i,q){
		cin>>t[i]>>x[i]>>y[i];
	}
	for(int L=0;L<q;L+=B){
		int R=min(q,L+B);
		for(int i=1;i<=m;i++)used[i]=0;
		for(int i=L;i<R;i++){
			if(t[i]==1)used[x[i]]=1;
		}
		vector<ll> S;//このクエリバケット内で変更がある辺のid
		vector<P> E;//変更のない辺{コスト,id}、降順にuniteしていく
		for(int i=1;i<=m;i++){
			if(used[i])S.push_back(i);
			else E.push_back(make_pair(c[i],i));
		}
		sort(all(E));
		vector<qry> Q;//バケット内のクエリ、wの降順に答えていく
		for(int i=L;i<R;i++){
			if(t[i]==2){
				Q.push_back((qry){x[i],y[i],i});
			}
		}
		sort(all(Q));
		uf::init();
		//cc[i][j]:=辺S[j]のクエリL+iの直前のコスト
		for(int i=0;i<S.size();i++){
			cc[0][i]=c[S[i]];
		}
		for(int i=L;i<R;i++){
			rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
			if(t[i]==1){
				cc[i-L+1][lower_bound(all(S),x[i])-S.begin()]=y[i];
			}
		}
		for(auto qs:Q){
			while(E.size()>0&&E.back().first>=qs.w){
				ll id=E.back().second;
				uf::unite(a[id],b[id]);
				E.pop_back();
			}
			uf::confirm();
			for(int i=0;i<S.size();i++){
				if(cc[qs.id-L][i]>=qs.w){
					uf::unite(a[S[i]],b[S[i]]);
				}
			}
			fans[qs.id]=uf::siz(qs.s);
			uf::rollback();
		}
		for(int i=L;i<R;i++){
			if(t[i]==1)c[x[i]]=y[i];
		}
	}
	for(int i=0;i<q;i++)if(t[i]==2)cout<<fans[i]<<"\n";
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<S.size();i++){
               ~^~~~~~~~~
bridges.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
bridges.cpp:98:8:
    rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
        ~~~~~~~~~~              
bridges.cpp:98:4: note: in expansion of macro 'rep'
    rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
    ^~~
bridges.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<S.size();i++){
                ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 42 ms 6008 KB Output is correct
4 Correct 17 ms 1016 KB Output is correct
5 Correct 25 ms 4856 KB Output is correct
6 Correct 24 ms 4856 KB Output is correct
7 Correct 26 ms 4856 KB Output is correct
8 Correct 29 ms 4856 KB Output is correct
9 Correct 30 ms 4856 KB Output is correct
10 Correct 30 ms 4856 KB Output is correct
11 Correct 29 ms 4856 KB Output is correct
12 Correct 32 ms 4856 KB Output is correct
13 Correct 37 ms 5112 KB Output is correct
14 Correct 33 ms 5112 KB Output is correct
15 Correct 30 ms 4892 KB Output is correct
16 Correct 27 ms 4856 KB Output is correct
17 Correct 28 ms 4856 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1738 ms 10076 KB Output is correct
2 Correct 1738 ms 12656 KB Output is correct
3 Correct 1743 ms 12720 KB Output is correct
4 Correct 1752 ms 12756 KB Output is correct
5 Correct 1745 ms 12976 KB Output is correct
6 Correct 2192 ms 13288 KB Output is correct
7 Correct 2213 ms 13304 KB Output is correct
8 Correct 2178 ms 13516 KB Output is correct
9 Correct 127 ms 3832 KB Output is correct
10 Correct 1550 ms 12004 KB Output is correct
11 Correct 1543 ms 11860 KB Output is correct
12 Correct 1454 ms 12356 KB Output is correct
13 Correct 1534 ms 13404 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1291 ms 8892 KB Output is correct
2 Correct 862 ms 9364 KB Output is correct
3 Correct 1482 ms 11124 KB Output is correct
4 Correct 1276 ms 11432 KB Output is correct
5 Correct 128 ms 3964 KB Output is correct
6 Correct 1375 ms 11380 KB Output is correct
7 Correct 1168 ms 11236 KB Output is correct
8 Correct 1129 ms 11280 KB Output is correct
9 Correct 963 ms 10348 KB Output is correct
10 Correct 898 ms 10212 KB Output is correct
11 Correct 1006 ms 11372 KB Output is correct
12 Correct 1000 ms 11224 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 7580 KB Output is correct
2 Correct 126 ms 2552 KB Output is correct
3 Correct 324 ms 5808 KB Output is correct
4 Correct 286 ms 5812 KB Output is correct
5 Correct 2054 ms 8312 KB Output is correct
6 Correct 2353 ms 7732 KB Output is correct
7 Correct 2058 ms 8388 KB Output is correct
8 Correct 1216 ms 5108 KB Output is correct
9 Correct 1190 ms 4976 KB Output is correct
10 Correct 1124 ms 5940 KB Output is correct
11 Correct 1864 ms 6796 KB Output is correct
12 Correct 1828 ms 6808 KB Output is correct
13 Correct 1688 ms 7644 KB Output is correct
14 Correct 1788 ms 8248 KB Output is correct
15 Correct 1963 ms 8460 KB Output is correct
16 Correct 2387 ms 7280 KB Output is correct
17 Correct 2403 ms 7536 KB Output is correct
18 Correct 2388 ms 7480 KB Output is correct
19 Correct 2358 ms 7388 KB Output is correct
20 Correct 1870 ms 7996 KB Output is correct
21 Correct 1899 ms 7996 KB Output is correct
22 Correct 2110 ms 8452 KB Output is correct
23 Correct 1955 ms 7824 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1738 ms 10076 KB Output is correct
2 Correct 1738 ms 12656 KB Output is correct
3 Correct 1743 ms 12720 KB Output is correct
4 Correct 1752 ms 12756 KB Output is correct
5 Correct 1745 ms 12976 KB Output is correct
6 Correct 2192 ms 13288 KB Output is correct
7 Correct 2213 ms 13304 KB Output is correct
8 Correct 2178 ms 13516 KB Output is correct
9 Correct 127 ms 3832 KB Output is correct
10 Correct 1550 ms 12004 KB Output is correct
11 Correct 1543 ms 11860 KB Output is correct
12 Correct 1454 ms 12356 KB Output is correct
13 Correct 1534 ms 13404 KB Output is correct
14 Correct 1291 ms 8892 KB Output is correct
15 Correct 862 ms 9364 KB Output is correct
16 Correct 1482 ms 11124 KB Output is correct
17 Correct 1276 ms 11432 KB Output is correct
18 Correct 128 ms 3964 KB Output is correct
19 Correct 1375 ms 11380 KB Output is correct
20 Correct 1168 ms 11236 KB Output is correct
21 Correct 1129 ms 11280 KB Output is correct
22 Correct 963 ms 10348 KB Output is correct
23 Correct 898 ms 10212 KB Output is correct
24 Correct 1006 ms 11372 KB Output is correct
25 Correct 1000 ms 11224 KB Output is correct
26 Correct 1830 ms 12792 KB Output is correct
27 Correct 2146 ms 12604 KB Output is correct
28 Correct 1854 ms 12932 KB Output is correct
29 Correct 1469 ms 12624 KB Output is correct
30 Correct 2005 ms 12548 KB Output is correct
31 Correct 2019 ms 12504 KB Output is correct
32 Correct 2105 ms 12632 KB Output is correct
33 Correct 1796 ms 12816 KB Output is correct
34 Correct 1801 ms 12780 KB Output is correct
35 Correct 1827 ms 12812 KB Output is correct
36 Correct 1513 ms 12688 KB Output is correct
37 Correct 1420 ms 12756 KB Output is correct
38 Correct 1430 ms 12932 KB Output is correct
39 Correct 1310 ms 11440 KB Output is correct
40 Correct 1316 ms 11476 KB Output is correct
41 Correct 1306 ms 11600 KB Output is correct
42 Correct 1308 ms 12756 KB Output is correct
43 Correct 1309 ms 12916 KB Output is correct
44 Correct 1307 ms 12872 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 42 ms 6008 KB Output is correct
4 Correct 17 ms 1016 KB Output is correct
5 Correct 25 ms 4856 KB Output is correct
6 Correct 24 ms 4856 KB Output is correct
7 Correct 26 ms 4856 KB Output is correct
8 Correct 29 ms 4856 KB Output is correct
9 Correct 30 ms 4856 KB Output is correct
10 Correct 30 ms 4856 KB Output is correct
11 Correct 29 ms 4856 KB Output is correct
12 Correct 32 ms 4856 KB Output is correct
13 Correct 37 ms 5112 KB Output is correct
14 Correct 33 ms 5112 KB Output is correct
15 Correct 30 ms 4892 KB Output is correct
16 Correct 27 ms 4856 KB Output is correct
17 Correct 28 ms 4856 KB Output is correct
18 Correct 1738 ms 10076 KB Output is correct
19 Correct 1738 ms 12656 KB Output is correct
20 Correct 1743 ms 12720 KB Output is correct
21 Correct 1752 ms 12756 KB Output is correct
22 Correct 1745 ms 12976 KB Output is correct
23 Correct 2192 ms 13288 KB Output is correct
24 Correct 2213 ms 13304 KB Output is correct
25 Correct 2178 ms 13516 KB Output is correct
26 Correct 127 ms 3832 KB Output is correct
27 Correct 1550 ms 12004 KB Output is correct
28 Correct 1543 ms 11860 KB Output is correct
29 Correct 1454 ms 12356 KB Output is correct
30 Correct 1534 ms 13404 KB Output is correct
31 Correct 1291 ms 8892 KB Output is correct
32 Correct 862 ms 9364 KB Output is correct
33 Correct 1482 ms 11124 KB Output is correct
34 Correct 1276 ms 11432 KB Output is correct
35 Correct 128 ms 3964 KB Output is correct
36 Correct 1375 ms 11380 KB Output is correct
37 Correct 1168 ms 11236 KB Output is correct
38 Correct 1129 ms 11280 KB Output is correct
39 Correct 963 ms 10348 KB Output is correct
40 Correct 898 ms 10212 KB Output is correct
41 Correct 1006 ms 11372 KB Output is correct
42 Correct 1000 ms 11224 KB Output is correct
43 Correct 2378 ms 7580 KB Output is correct
44 Correct 126 ms 2552 KB Output is correct
45 Correct 324 ms 5808 KB Output is correct
46 Correct 286 ms 5812 KB Output is correct
47 Correct 2054 ms 8312 KB Output is correct
48 Correct 2353 ms 7732 KB Output is correct
49 Correct 2058 ms 8388 KB Output is correct
50 Correct 1216 ms 5108 KB Output is correct
51 Correct 1190 ms 4976 KB Output is correct
52 Correct 1124 ms 5940 KB Output is correct
53 Correct 1864 ms 6796 KB Output is correct
54 Correct 1828 ms 6808 KB Output is correct
55 Correct 1688 ms 7644 KB Output is correct
56 Correct 1788 ms 8248 KB Output is correct
57 Correct 1963 ms 8460 KB Output is correct
58 Correct 2387 ms 7280 KB Output is correct
59 Correct 2403 ms 7536 KB Output is correct
60 Correct 2388 ms 7480 KB Output is correct
61 Correct 2358 ms 7388 KB Output is correct
62 Correct 1870 ms 7996 KB Output is correct
63 Correct 1899 ms 7996 KB Output is correct
64 Correct 2110 ms 8452 KB Output is correct
65 Correct 1955 ms 7824 KB Output is correct
66 Correct 1830 ms 12792 KB Output is correct
67 Correct 2146 ms 12604 KB Output is correct
68 Correct 1854 ms 12932 KB Output is correct
69 Correct 1469 ms 12624 KB Output is correct
70 Correct 2005 ms 12548 KB Output is correct
71 Correct 2019 ms 12504 KB Output is correct
72 Correct 2105 ms 12632 KB Output is correct
73 Correct 1796 ms 12816 KB Output is correct
74 Correct 1801 ms 12780 KB Output is correct
75 Correct 1827 ms 12812 KB Output is correct
76 Correct 1513 ms 12688 KB Output is correct
77 Correct 1420 ms 12756 KB Output is correct
78 Correct 1430 ms 12932 KB Output is correct
79 Correct 1310 ms 11440 KB Output is correct
80 Correct 1316 ms 11476 KB Output is correct
81 Correct 1306 ms 11600 KB Output is correct
82 Correct 1308 ms 12756 KB Output is correct
83 Correct 1309 ms 12916 KB Output is correct
84 Correct 1307 ms 12872 KB Output is correct
85 Correct 2937 ms 16024 KB Output is correct
86 Correct 387 ms 12912 KB Output is correct
87 Correct 334 ms 12760 KB Output is correct
88 Correct 2608 ms 14912 KB Output is correct
89 Correct 2927 ms 16092 KB Output is correct
90 Correct 2534 ms 15320 KB Output is correct
91 Correct 1853 ms 12808 KB Output is correct
92 Correct 1850 ms 12764 KB Output is correct
93 Correct 2327 ms 13624 KB Output is correct
94 Correct 2353 ms 14984 KB Output is correct
95 Correct 2358 ms 15144 KB Output is correct
96 Correct 2407 ms 15468 KB Output is correct
97 Correct 2211 ms 14136 KB Output is correct
98 Correct 2402 ms 15172 KB Output is correct
99 Correct 2820 ms 16240 KB Output is correct
100 Correct 2822 ms 16032 KB Output is correct
101 Correct 2875 ms 16144 KB Output is correct
102 Correct 2860 ms 16352 KB Output is correct
103 Correct 2642 ms 15896 KB Output is correct
104 Correct 2646 ms 16064 KB Output is correct
105 Correct 2230 ms 15688 KB Output is correct
106 Correct 1957 ms 15308 KB Output is correct
107 Correct 2111 ms 14908 KB Output is correct
108 Correct 2605 ms 16472 KB Output is correct
109 Correct 2391 ms 14452 KB Output is correct