Submission #279587

#	Time	Username	Problem	Language	Result	Execution time	Memory
279587		Nodir_Bobiev	Bridges (APIO19_bridges)	C++17	43 / 100	1208 ms	24740 KiB

bridges

/*
+----------------------------------------------------------------+
| In the name of Allah, the most Gracious and the most Merciful. |
+----------------------------------------------------------------+
When you are down in your misery
And there is nowhere to run
Remember just remember
You can always run to The One.
When things are down
And you are out of your mind
Remember just remember
Allah is The Kind.
*/
# include <bits/stdc++.h>
# define FILE
using namespace std;

const int N = 5e4 + 100;
int n, m, q, p[N], cnt[N], used[N], V[2*N], U[2*N], W[2*N], seg[4*N];
bool sub2 = true, sub4 = true;
vector < vector < int > > gr[N];
vector < vector < int > > queires;

int dfs( int x, int v, int w ){
	used[v] = x;
	int cnt = 1;
	for( auto to: gr[v] ){
		if( W[to[1]] >= w && used[to[0]] != x){
			cnt += dfs(x, to[0], w);
		}
	}return cnt;
}
void Subtask1(){
	for( int i = 1; i <= m; i ++ ){
		gr[V[i]].push_back( {U[i], i} );
    	gr[U[i]].push_back( {V[i], i} );
	}
	for( int i = 1; i <= q; i ++ ){
		if( queires[i-1][0] == 1 ){
			W[queires[i-1][1]] = queires[i-1][2];
		}
		else{
			cout << dfs(i, queires[i-1][1], queires[i-1][2]) << endl;
		}
	}
	exit( 0 );
}


void build(int tl=1, int tr=n, int td=1 ){
	if( tl ==tr ) seg[td] = W[tl];
	else{
		int tm = (tl+tr)>>1;
		build(tl, tm, td+td); build(tm+1, tr,td+td+1);
		seg[td] = min(seg[td+td], seg[td+td+1]);
	}
}
int get( int l, int r, int tl=1, int tr=n, int td=1 ){
	//cout << l << ' '<< r << ' ' << tl << ' ' << tr << ' ' << td << ' ' << seg[td] << endl;
	if( l > r || tl > tr || l > tr || tl > r ) return 1e9;
	if( l <= tl && tr <= r ) return seg[td];
	else{
		int tm = (tl+tr)>>1;
		return min( get(l,r,tl,tm,td+td),get(l,r,tm+1,tr,td+td+1) );
	}
}
void update(int x, int val, int tl=1, int tr=n, int td=1){
	if(x < tl || tr < x )return;
	if(tl==tr)seg[td] = val;
	else{
		int tm = (tl+tr)>>1;
		update(x, val, tl, tm, td+td ); update(x, val, tm+1, tr, td+td+1);
		seg[td] = min(seg[td+td], seg[td+td+1] );
	}
}
void Subtask2(){
	build();
	for( auto query: queires ){
		int t = query[0];
		if( t == 1 ){
			int b = query[1], r = query[2];
			update(b, r);
		}else{
			int s = query[1], w = query[2];
			int ll = 0, rr = s;
			while( rr-ll > 1 ){
				int mm = (ll+rr)>>1;
				//cout << "left " << ll << ' ' << rr << ' ' << mm << ' ' << get(mm, s-1) << endl;
				if( get(mm, s-1) >= w )rr = mm;
				else ll = mm;
				//cout << "left " << ll << ' '<< rr<<endl;
			}
			int left = rr;
			ll = s-1, rr = n;
			while(rr-ll>1){
				int mm=(ll+rr)>>1;
				//cout << "right " << ll <<' '<<rr<<' ' <<mm<< ' '<< get(s, mm) << endl;
				if( get(s, mm) >= w )ll = mm;
				else rr = mm;
			}int right = ll;
			cout << right - left + 2 << endl;
		}
	}
	exit(0);
}


int get( int x ){
	if( p[x] == x ) return x;
	else return p[x] = get( p[x] );
}
void unin( int x, int y ){
	//cout << x << ' '<< y << endl;
	x = get( x );
	y = get( y );
	if( x == y ) return;
	p[x] = y;
	cnt[y] += cnt[x];
	//cout << "unin" << endl;
}
void Subtask4(){
	vector < vector < int > > edges;
	vector < vector < int > > quries;
	vector < int > ans(q, 1);
	for( int i = 1; i <= m; i ++ ){
		edges.push_back({W[i], V[i], U[i]});
	}
	for( int i = 0; i < q; i ++ ){
		quries.push_back({queires[i][2], queires[i][1], i});
	}
	sort( edges.rbegin(), edges.rend() );
	sort( quries.rbegin(), quries.rend() );
	int id = 0;
	for( int i = 1; i <= n; i ++ ){
		p[i] = i;
		cnt[i] = 1;
	}
	for( int i = 0; i < q; i ++ ){
		/*cout<<"-- "<<i<<' '<<quries[i][0] <<' '<< quries[i][1] << ' ' << quries[i][2]<<endl;
		if( id < m )
		cout <<"--- "<<id<<' '<<edges[id][0]<<' '<<edges[id][1]<<' '<<edges[id][2]<<endl;
		*/
		while( id < m && edges[id][0] >= quries[i][0] ){
			unin(edges[id][1], edges[id][2]);
			id++;
		}
		
		ans[quries[i][2]] = cnt[get(quries[i][1])];
		//cout << "afterward" << endl;
	}
	//cout << "lolo" << endl;
	for( int i = 0; i < q; i ++ ){
		cout << ans[i] << endl;
	}
	exit(0);	
}
int main(){
    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for( int i = 1; i <= m; i ++ ){
    	cin >> V[i] >> U[i] >> W[i];
    	if( V[i] != i || U[i]!= i+1 )
    		sub2 = false;
    }
    cin >> q;
    for(int i = 1; i <= q; i ++ ){
    	int t, a, b; cin >> t >> a >> b;
    	queires.push_back({t,a,b});
    	if( t == 1 ) sub4 = false;
    }
    if( n <= 1000 && m <= 1000 && q <= 10000){
    	Subtask1();
    }
    if( sub2 ){
    	Subtask2();
    }
    if( sub4 ){
    	Subtask4();
    }


}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27