oj.uz

Submission #135047

# Submission time Handle Problem Language Result Execution time Memory
135047 2019-07-23T14:59:37 Z ryansee Bridges (APIO19_bridges) C++14
100 / 100
 2984 ms 10316 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native,avx2,fma")
 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006/3)
#define ll /*long long*/ int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define emp emplace
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n,m,q;
struct edge {
	ll a,b,w,i,in;
	bool operator < (const edge &e) const {
		return w>e.w;
	}
};
edge edges[MAXN];
int pos[MAXN];
struct query {
	ll b,r,i,q,f;
	bool operator < (const query &e) const {
		if(b!=e.b)return b<e.b;
		return i<e.i;
	} 
}; vector<query>bkts[203];
ll magic=500,co=0; ll other=203;
deque<spi>Q;
stack<ll>stk;
struct ufds_ {
	int p[MAXN],sz[MAXN];
	ufds_() { FOR(i,0,n+1)p[i]=i,sz[i]=1; }
	void merge_b4(ll x, ll y){
		x=find_real(x),y=find_real(y);
		if(x==y)return;
		p[x]=y;
		sz[y]+=sz[x];
	}
	ll find_real(ll x) { return (p[x]==x)?x:p[x]=find_real(p[x]);}
	void fake_merge(ll x, ll y) {
		x=find_fake(x),y=find_fake(y);
		if(x==y)return;
		if(sz[x]>sz[y])swap(x,y);//sz[x]<=sz[y];
		p[x]=y;
		sz[y]+=sz[x];
		stk.ph(x);
	}
	ll find_fake(ll x) { return (p[x]==x)?x:find_fake(p[x]);}
	void rollback(){
		while(stk.size()){
			sz[p[stk.top()]]-=sz[stk.top()];
			p[stk.top()]=stk.top();
			stk.pop();
		}
		return;
	}
} ufds;
int ans[MAXN];
int main()
{ mmst(ans,-1);
	FAST
	cin>>n>>m;
	FOR(i,0,m){
		cin>>edges[i].a>>edges[i].b>>edges[i].w;edges[i].i=i;edges[i].in=1;
	}
	sort(edges,edges+m);
	FOR(i,0,m)pos[edges[i].i]=i;
	cin>>q;
	FOR(i,0,q){
		ll t;cin>>t;
		if(t==1){
			ll b,r;cin>>b>>r;--b;
			bkts[co].pb({b,r,i,0});
			if(bkts[co].size()>magic)++co;
		} else {
			ll p,w;cin>>p>>w;
			bkts[co].pb({p,w,i,1});
			if(bkts[co].size()>magic)++co;
		}
	}
	ufds=ufds_();
	FOR(bk,0,other){ if(bkts[bk].empty())break; 
		for(auto i:bkts[bk]){
			if(!i.q)edges[pos[i.b]].in=0;
		}
		vector<query>hmm,handle;
		for(auto i:bkts[bk]){
			if(i.q)hmm.pb(i);
			else handle.pb(i);
		}
		sort(all(hmm),[](query x, query y){return x.r>y.r;});ufds=ufds_();
		sort(all(handle)); FOR(i,1,siz(handle))if(handle[i-1].b==handle[i].b)handle[i].f=1;
		ll co=0;
		for(auto i:hmm){ 
			while(co<m&&edges[co].w>=i.r){
				if(edges[co].in)ufds.merge_b4(edges[co].a,edges[co].b);
				++co;
			}
			auto tmp=i;
			FOR(i,0,siz(handle))handle[i].q=0;
			FOR(i,0,siz(handle)-1)if(handle[i+1].b==handle[i].b&&handle[i+1].i<tmp.i)handle[i].q=1;
			for(auto j:handle)if(!j.q&&((j.i<i.i&&j.r>=i.r)||(j.i>i.i&&edges[pos[j.b]].w>=i.r&&!j.f))){
				ufds.fake_merge(edges[pos[j.b]].a,edges[pos[j.b]].b);
			}
			// cerr<<i.i<<' '<<co<<' '<<ufds.find_fake(1)<<' '<<ufds.find_fake(2)<<' '<<ufds.find_fake(3)<<' '<<ufds.sz[1]<<' '<<ufds.sz[2]<<' '<<ufds.sz[3]<<'\n';
			ans[i.i]=ufds.sz[ufds.find_fake(i.b)];
			ufds.rollback();
		}
		for(auto i:bkts[bk])if(!i.q){
			edges[pos[i.b]].in=1;
			edges[pos[i.b]].w=i.r;
		}
		sort(edges,edges+m);
		FOR(i,0,m)pos[edges[i].i]=i;
	}
	FOR(i,0,q)if(~ans[i]){
		cout<<ans[i]<<'\n';
	}
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
*/
/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3
* 
* 5 2
4 3 3
4 1 10
5
2 1 5 
1 2 9
1 1 6
1 1 2
2 3 4
* 
* Ans:
* 1
* 
* 5 2
4 3 3
4 1 10
8
2 1 5
1 2 2
1 2 9
1 1 6
1 1 2
2 3 4
1 1 3
2 1 6
 
*/

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:101:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(bkts[co].size()>magic)++co;
       ~~~~~~~~~~~~~~~^~~~~~
bridges.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(bkts[co].size()>magic)++co;
       ~~~~~~~~~~~~~~~^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 25 ms 1912 KB Output is correct
4 Correct 9 ms 1756 KB Output is correct
5 Correct 24 ms 1912 KB Output is correct
6 Correct 20 ms 1788 KB Output is correct
7 Correct 24 ms 1824 KB Output is correct
8 Correct 29 ms 1784 KB Output is correct
9 Correct 23 ms 1784 KB Output is correct
10 Correct 26 ms 1784 KB Output is correct
11 Correct 26 ms 1784 KB Output is correct
12 Correct 27 ms 1784 KB Output is correct
13 Correct 29 ms 1788 KB Output is correct
14 Correct 28 ms 1912 KB Output is correct
15 Correct 27 ms 1824 KB Output is correct
16 Correct 23 ms 1784 KB Output is correct
17 Correct 24 ms 1784 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1448 ms 5188 KB Output is correct
2 Correct 1383 ms 5444 KB Output is correct
3 Correct 1377 ms 5212 KB Output is correct
4 Correct 1432 ms 5272 KB Output is correct
5 Correct 1450 ms 5184 KB Output is correct
6 Correct 1827 ms 5448 KB Output is correct
7 Correct 1827 ms 5440 KB Output is correct
8 Correct 1823 ms 5456 KB Output is correct
9 Correct 57 ms 3832 KB Output is correct
10 Correct 1200 ms 5316 KB Output is correct
11 Correct 1136 ms 5308 KB Output is correct
12 Correct 1196 ms 5576 KB Output is correct
13 Correct 1250 ms 5200 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1250 ms 4640 KB Output is correct
2 Correct 897 ms 4012 KB Output is correct
3 Correct 1720 ms 4784 KB Output is correct
4 Correct 1398 ms 4828 KB Output is correct
5 Correct 59 ms 3832 KB Output is correct
6 Correct 1595 ms 4828 KB Output is correct
7 Correct 1376 ms 4728 KB Output is correct
8 Correct 1176 ms 4680 KB Output is correct
9 Correct 1042 ms 5060 KB Output is correct
10 Correct 936 ms 5064 KB Output is correct
11 Correct 1082 ms 4660 KB Output is correct
12 Correct 936 ms 4728 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1665 ms 6748 KB Output is correct
2 Correct 59 ms 3832 KB Output is correct
3 Correct 109 ms 4216 KB Output is correct
4 Correct 115 ms 4088 KB Output is correct
5 Correct 1783 ms 6736 KB Output is correct
6 Correct 1732 ms 6728 KB Output is correct
7 Correct 1773 ms 6732 KB Output is correct
8 Correct 687 ms 5300 KB Output is correct
9 Correct 715 ms 5304 KB Output is correct
10 Correct 709 ms 5436 KB Output is correct
11 Correct 1121 ms 6020 KB Output is correct
12 Correct 1096 ms 6040 KB Output is correct
13 Correct 1096 ms 6168 KB Output is correct
14 Correct 1854 ms 6864 KB Output is correct
15 Correct 1827 ms 6876 KB Output is correct
16 Correct 1648 ms 6776 KB Output is correct
17 Correct 1669 ms 6712 KB Output is correct
18 Correct 1560 ms 6716 KB Output is correct
19 Correct 1571 ms 6648 KB Output is correct
20 Correct 1295 ms 6468 KB Output is correct
21 Correct 1247 ms 6520 KB Output is correct
22 Correct 1550 ms 6736 KB Output is correct
23 Correct 1299 ms 6360 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1448 ms 5188 KB Output is correct
2 Correct 1383 ms 5444 KB Output is correct
3 Correct 1377 ms 5212 KB Output is correct
4 Correct 1432 ms 5272 KB Output is correct
5 Correct 1450 ms 5184 KB Output is correct
6 Correct 1827 ms 5448 KB Output is correct
7 Correct 1827 ms 5440 KB Output is correct
8 Correct 1823 ms 5456 KB Output is correct
9 Correct 57 ms 3832 KB Output is correct
10 Correct 1200 ms 5316 KB Output is correct
11 Correct 1136 ms 5308 KB Output is correct
12 Correct 1196 ms 5576 KB Output is correct
13 Correct 1250 ms 5200 KB Output is correct
14 Correct 1250 ms 4640 KB Output is correct
15 Correct 897 ms 4012 KB Output is correct
16 Correct 1720 ms 4784 KB Output is correct
17 Correct 1398 ms 4828 KB Output is correct
18 Correct 59 ms 3832 KB Output is correct
19 Correct 1595 ms 4828 KB Output is correct
20 Correct 1376 ms 4728 KB Output is correct
21 Correct 1176 ms 4680 KB Output is correct
22 Correct 1042 ms 5060 KB Output is correct
23 Correct 936 ms 5064 KB Output is correct
24 Correct 1082 ms 4660 KB Output is correct
25 Correct 936 ms 4728 KB Output is correct
26 Correct 1998 ms 5316 KB Output is correct
27 Correct 2106 ms 5308 KB Output is correct
28 Correct 1879 ms 5328 KB Output is correct
29 Correct 1485 ms 5180 KB Output is correct
30 Correct 1914 ms 5312 KB Output is correct
31 Correct 1933 ms 5456 KB Output is correct
32 Correct 1977 ms 5316 KB Output is correct
33 Correct 1707 ms 5192 KB Output is correct
34 Correct 1708 ms 5240 KB Output is correct
35 Correct 1727 ms 5188 KB Output is correct
36 Correct 1422 ms 5176 KB Output is correct
37 Correct 1417 ms 5192 KB Output is correct
38 Correct 1423 ms 5184 KB Output is correct
39 Correct 1202 ms 5340 KB Output is correct
40 Correct 1185 ms 5320 KB Output is correct
41 Correct 1186 ms 5316 KB Output is correct
42 Correct 1147 ms 5188 KB Output is correct
43 Correct 1168 ms 5240 KB Output is correct
44 Correct 1215 ms 5248 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 25 ms 1912 KB Output is correct
4 Correct 9 ms 1756 KB Output is correct
5 Correct 24 ms 1912 KB Output is correct
6 Correct 20 ms 1788 KB Output is correct
7 Correct 24 ms 1824 KB Output is correct
8 Correct 29 ms 1784 KB Output is correct
9 Correct 23 ms 1784 KB Output is correct
10 Correct 26 ms 1784 KB Output is correct
11 Correct 26 ms 1784 KB Output is correct
12 Correct 27 ms 1784 KB Output is correct
13 Correct 29 ms 1788 KB Output is correct
14 Correct 28 ms 1912 KB Output is correct
15 Correct 27 ms 1824 KB Output is correct
16 Correct 23 ms 1784 KB Output is correct
17 Correct 24 ms 1784 KB Output is correct
18 Correct 1448 ms 5188 KB Output is correct
19 Correct 1383 ms 5444 KB Output is correct
20 Correct 1377 ms 5212 KB Output is correct
21 Correct 1432 ms 5272 KB Output is correct
22 Correct 1450 ms 5184 KB Output is correct
23 Correct 1827 ms 5448 KB Output is correct
24 Correct 1827 ms 5440 KB Output is correct
25 Correct 1823 ms 5456 KB Output is correct
26 Correct 57 ms 3832 KB Output is correct
27 Correct 1200 ms 5316 KB Output is correct
28 Correct 1136 ms 5308 KB Output is correct
29 Correct 1196 ms 5576 KB Output is correct
30 Correct 1250 ms 5200 KB Output is correct
31 Correct 1250 ms 4640 KB Output is correct
32 Correct 897 ms 4012 KB Output is correct
33 Correct 1720 ms 4784 KB Output is correct
34 Correct 1398 ms 4828 KB Output is correct
35 Correct 59 ms 3832 KB Output is correct
36 Correct 1595 ms 4828 KB Output is correct
37 Correct 1376 ms 4728 KB Output is correct
38 Correct 1176 ms 4680 KB Output is correct
39 Correct 1042 ms 5060 KB Output is correct
40 Correct 936 ms 5064 KB Output is correct
41 Correct 1082 ms 4660 KB Output is correct
42 Correct 936 ms 4728 KB Output is correct
43 Correct 1665 ms 6748 KB Output is correct
44 Correct 59 ms 3832 KB Output is correct
45 Correct 109 ms 4216 KB Output is correct
46 Correct 115 ms 4088 KB Output is correct
47 Correct 1783 ms 6736 KB Output is correct
48 Correct 1732 ms 6728 KB Output is correct
49 Correct 1773 ms 6732 KB Output is correct
50 Correct 687 ms 5300 KB Output is correct
51 Correct 715 ms 5304 KB Output is correct
52 Correct 709 ms 5436 KB Output is correct
53 Correct 1121 ms 6020 KB Output is correct
54 Correct 1096 ms 6040 KB Output is correct
55 Correct 1096 ms 6168 KB Output is correct
56 Correct 1854 ms 6864 KB Output is correct
57 Correct 1827 ms 6876 KB Output is correct
58 Correct 1648 ms 6776 KB Output is correct
59 Correct 1669 ms 6712 KB Output is correct
60 Correct 1560 ms 6716 KB Output is correct
61 Correct 1571 ms 6648 KB Output is correct
62 Correct 1295 ms 6468 KB Output is correct
63 Correct 1247 ms 6520 KB Output is correct
64 Correct 1550 ms 6736 KB Output is correct
65 Correct 1299 ms 6360 KB Output is correct
66 Correct 1998 ms 5316 KB Output is correct
67 Correct 2106 ms 5308 KB Output is correct
68 Correct 1879 ms 5328 KB Output is correct
69 Correct 1485 ms 5180 KB Output is correct
70 Correct 1914 ms 5312 KB Output is correct
71 Correct 1933 ms 5456 KB Output is correct
72 Correct 1977 ms 5316 KB Output is correct
73 Correct 1707 ms 5192 KB Output is correct
74 Correct 1708 ms 5240 KB Output is correct
75 Correct 1727 ms 5188 KB Output is correct
76 Correct 1422 ms 5176 KB Output is correct
77 Correct 1417 ms 5192 KB Output is correct
78 Correct 1423 ms 5184 KB Output is correct
79 Correct 1202 ms 5340 KB Output is correct
80 Correct 1185 ms 5320 KB Output is correct
81 Correct 1186 ms 5316 KB Output is correct
82 Correct 1147 ms 5188 KB Output is correct
83 Correct 1168 ms 5240 KB Output is correct
84 Correct 1215 ms 5248 KB Output is correct
85 Correct 2984 ms 6484 KB Output is correct
86 Correct 198 ms 6024 KB Output is correct
87 Correct 130 ms 6104 KB Output is correct
88 Correct 2142 ms 8780 KB Output is correct
89 Correct 2975 ms 10316 KB Output is correct
90 Correct 2133 ms 9024 KB Output is correct
91 Correct 1644 ms 7860 KB Output is correct
92 Correct 1679 ms 7988 KB Output is correct
93 Correct 2088 ms 7912 KB Output is correct
94 Correct 2115 ms 9060 KB Output is correct
95 Correct 2267 ms 9212 KB Output is correct
96 Correct 2168 ms 9036 KB Output is correct
97 Correct 1954 ms 9008 KB Output is correct
98 Correct 1959 ms 8724 KB Output is correct
99 Correct 2930 ms 10220 KB Output is correct
100 Correct 2919 ms 10180 KB Output is correct
101 Correct 2865 ms 10304 KB Output is correct
102 Correct 2834 ms 10296 KB Output is correct
103 Correct 2339 ms 9464 KB Output is correct
104 Correct 2330 ms 9568 KB Output is correct
105 Correct 2024 ms 9312 KB Output is correct
106 Correct 1727 ms 8964 KB Output is correct
107 Correct 1901 ms 9592 KB Output is correct
108 Correct 2835 ms 10084 KB Output is correct
109 Correct 1641 ms 8184 KB Output is correct