Submission #1086024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086024		peacebringer1667	Bridges (APIO19_bridges)	C++17	43 / 100	364 ms	9144 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 5e4 + 5;
const int maxQ = 1e5 + 5;

struct DSU{
	int par[maxn],sz[maxn];
	
	void init(int n){
		for (int i = 1 ; i <= n ; i++){
			par[i] = i;
			sz[i] = 1;
		}
	}
	
	int findp(int x){
		return (x == par[x]) ? x : par[x] = findp(par[x]);
	}
	
	void add(int u,int v){
		int x = findp(u),y = findp(v);
		if (x != y){
			par[y] = x;
			sz[x] += sz[y];
		}
	}
} dsu;

struct CTDL{
	int u = 0,v = 0,w = 0;
	bool operator <(const CTDL&other) const{
		return (w > other.w) || (w == other.w && u < other.u);
	}
};

struct query{
	int type = 0,v1 = 0,v2 = 0;
};

vector <CTDL> E,edge;
query Q[maxQ];
void input(int n,int m){
	while (m--){
		int u,v,w;
		cin >> u >> v >> w;
		E.push_back({u,v,w});
	}
}

namespace sub1{
	bool check(int n,int m,int q){
		return (max(n,m) <= 1000) && (q <= 10000); 
	}
	
	void TH1(int n,int m,int b,int r){
		E[b - 1].w = r;
	}
	
	int TH2(int n,int m,int s,int w){
		dsu.init(n);
		edge = E;sort(edge.begin(),edge.end());
		
		for (CTDL t : edge)
		  if (t.w >= w)
		    dsu.add(t.u,t.v);
		  else
		    break;
		
		return dsu.sz[dsu.findp(s)];
	}
	
	void solve(int n,int m,int q){
		dsu.init(n);
		for (int i = 1 ; i <= q ; i++){
			if (Q[i].type == 1)
			  TH1(n,m,Q[i].v1,Q[i].v2);
			else
			  cout << TH2(n,m,Q[i].v1,Q[i].v2) << "\n";
		}
	}
}

namespace sub4{
	bool check(int n,int m,int q){
		for (int i = 1 ; i <= q ; i++)
		  if (Q[i].type == 1) return 0;
		return 1;
	}
	
	int res[maxQ];

    void solve(int n,int m,int q){
    	for (int i = 1 ; i <= q ; i++)
    	  E.push_back({Q[i].v1 + n,i,Q[i].v2});
    	
    	sort(E.begin(),E.end());
    	dsu.init(n);
    	
    	for (CTDL t : E)
    	  if (t.u > n){
    	  	 t.u -= n;
    	  	 res[t.v] = dsu.sz[dsu.findp(t.u)];
		  }
		  else
		    dsu.add(t.u,t.v);
		
		for (int i = 1 ; i <= q ; i++) cout << res[i] << "\n";
	}
}

namespace sub2{
	const int inf = 1e9 + 1e8;
	
	struct segment_tree{
		int seg[4*maxn];
		
		void update(int l,int r,int v,int p,int val){
			if (l > p || r < p) return;
			if (l == r){
				seg[v] = val;
				return;
			}
			
			int w = (l + r)/2;
			update(l,w,2*v + 1,p,val);
			update(w + 1,r,2*v + 2,p,val);
			
			seg[v] = min(seg[2*v + 1],seg[2*v + 2]);
		}
		
		int calc(int l,int r,int v,int lx,int rx){
			if (l > rx || r < lx) return inf;
			if (l >= lx && r <= rx) return seg[v];
			
			int w = (l + r)/2;
			return min(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
		}
	} seg;
	
	void TH1(int n,int m,int e,int nw){
		int u = E[e - 1].u;
		seg.update(1,n,0,u,nw);
		E[e - 1].w = u;
	}
	
	void TH2(int n,int m,int s,int len){
		int v1 = 1,v2 = 1,l = 0,r = 0;
		
		l = 1,r = s - 1;
		while (l <= r){
			int w = (l + r)/2;
			if (seg.calc(1,n,0,w,s - 1) >= len){
				v1 = s - w + 1;
				r = w - 1;
			}
			else l = w + 1;
		}
		
		l = s + 1,r = n;
		while (l <= r){
			int w = (l + r)/2;
			if (seg.calc(1,n,0,s,w - 1) >= len){
				v2 = w - s + 1;
				l = w + 1;
			}
			else r = w - 1;
		}
		
		cout << v1 + v2 - 1 << "\n";
	}
	
	void desperation(int q){
		for (int i = 1 ; i <= q ; i++)
		  if (Q[i].type == 2) cout << 1 << "\n";
	}	
	void solve(int n,int m,int q){
		if (n == 1){
			desperation(q);
			return;
		}
		seg.update(1,n,0,n,inf);
		for (int i = 0 ; i < m ; i++)
		  seg.update(1,n,0,E[i].u,E[i].w);
		
		for (int i = 1 ; i <= q ; i++)
		  if (Q[i].type == 1)
		    TH1(n,m,Q[i].v1,Q[i].v2);
		  else
		    TH2(n,m,Q[i].v1,Q[i].v2);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,m,q;
	cin >> n >> m;
	input(n,m);
	cin >> q;
	for (int i = 1 ; i <= q ; i++) cin >> Q[i].type >> Q[i].v1 >> Q[i].v2;

    //sub : sub 1,4 brute force
	if (sub1::check(n,m,q)){
	  sub1::solve(n,m,q);
      return 0;
	} 
	
	if (sub4::check(n,m,q)){
		sub4::solve(n,m,q);
		return 0;
   	}
	
	sub2::solve(n,m,q);

	return 0;
}

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