Submission #1257079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257079		_rain_	Bridges (APIO19_bridges)	C++20	29 / 100	478 ms	5700 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = (int)5e4;
const int M = (int)1e5;

struct QUESTION{
	int t;
	int x , y;
	void read(){
		cin >> t >> x >> y;
		return ;
	}
} queri[M + 2];

int n , m , q;
	int x[M + 2] , y[M + 2] , w[M + 2];

namespace subtask1{
	bool check(){
		return n <= 1e3 && m <= 1e3 && q <= 1e4;
	}
	
	vector<int>ke[N+2];
		void add_canh(int u , int v , int id){
			ke[u].push_back(id) , ke[v].push_back(id);
			return ;
		}
		
	int ans = 0;
	bool vis[N + 2] = {};
		
		void dfs(int u , int p , int limit,bool t){
			++ans;
			vis[u] = t;
			for(auto& id : ke[u]){
				int v = x[id] ^ y[id] ^ u;
				if (vis[v]==t) continue;
				if (w[id] < limit) continue;
				dfs(v,u,limit,t);
			}
			return;
		}
	
	void main_code(){
		for(int i = 1; i <= m; ++i) add_canh(x[i] , y[i] , i);
		for(int i = 1; i <= q; ++i){
			int t = queri[i].t;
			if (t==1) w[queri[i].x] = queri[i].y;
			else {
				ans = 0;
				dfs(queri[i].x , 0 , queri[i].y,1);
				cout << ans << '\n';
				dfs(queri[i].x,0,queri[i].y,0);
			}
		}
	}
}

namespace subtask2{
	bool check(){
		for(int i = 1; i <= q; ++i) if (queri[i].t==1) return false;
		return true;
	}
	
	int par[N + 2] = {} , sz[N + 2] = {};
		int Find(int u){
			return par[u] == u ? par[u] : par[u] = Find(par[u]);
		}
		void unite(int u , int v){
			u = Find(u) , v = Find(v);
			if (u == v) return ;
			if (sz[v] > sz[u]) swap(u,v);
			par[v] = u , sz[u] += sz[v];
			return;
		}
	
	int id[2][M + 2];
	
	void main_code(){
		for(int i = 1; i <= n; ++i) par[i] = i , sz[i] = 1;
		for(int i = 1; i <= m; ++i)id[0][i] = i;
		for(int i = 1; i <= q; ++i) id[1][i] = i;
		sort(id[0]+1,id[0]+m+1,[&](int i , int j){
			return w[i] > w[j];
		});
		sort(id[1]+1,id[1]+q+1,[&](int i , int j){
			return queri[i].y < queri[j].y;	
		});
		for(int i = 1 , j = 1; i <= q; ++i){
			while (j <= m && w[id[0][j]] >= queri[id[1][i]].y) {
				unite(x[id[0][j]] , y[id[0][j]]);
				++j;
			}
			int u = queri[id[1][i]].x;
			cout << sz[Find(u)] << '\n';
		}
	}
}

namespace subtask3{
	bool check(){
		if (m != n - 1) return false;
		for(int i = 1; i <= m; ++i) {
			if (x[i] != i || y[i] != i + 1) return false;
		}
		return true;
	}
	
	int st[M*4+2];
		void upd(int id , int l , int r , int pos , int val){
			if (l > pos || r < pos) return;
			if (l == r) {
				st[id] = val;
			}
			else {
				int m = (l+r)/2;
				if (pos <= m) upd(id*2,l,m,pos,val);
					else upd(id*2+1,m+1,r,pos,val);
				st[id] = min(st[id*2] , st[id*2+1]);
			}
			return;
		}
		int Get(int id , int l , int r , int u , int v){
			if (l > v || r < u) return (int)1e9+7;
			if (u <= l && r <= v) return st[id];
			int m = (l+r)/2;
			return min(Get(id*2,l,m,u,v),Get(id*2+1,m+1,r,u,v));
		}
	
	int cnp_lef(int l , int r , int limit){
		int low = l , high = r - 1 , pos = r ;
		while (low<=high){
			int mid = low + high >> 1;
			int val = Get(1,1,m,mid,r-1);
			if (val >= limit){
				pos = mid;
				high = mid - 1;
			}
			else low = mid + 1;
		}
		return pos ;
	}
	
	int cnp_rig(int l , int r , int limit){
		int low = l , high = r , pos = l - 1;
		while (low<=high){
			int mid = low + high >> 1;
			int val = Get(1,1,m,l,mid);
//			cout << l << ' ' << mid << ' ' << val << '\n';
			if (val >= limit){
				pos = mid;
				low = mid + 1;
			}
			else high = mid - 1;
		}
		return pos + 1;
	}
	
	void main_code(){
		for(int i = 1; i <= m; ++i) upd(1,1,m,i,w[i]);
		for(int i = 1; i <= q; ++i){
			int t = queri[i].t , x = queri[i].x , y = queri[i].y;
			if (t==1) upd(1,1,m,x,y) , w[x] = y;
			if (t==2){
				int id_canh = x ;
				if (m==0) {
					cout << 1 << '\n';
					continue;
				}
				int lef = cnp_lef(1 , id_canh , y);
				int rig = cnp_rig(id_canh , m , y);
//				cout << lef << ' ' << rig << '\n';
//				cout << y << '\n';
				
				cout << i - lef + (rig - i + 1) << '\n';
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> m;
		for(int i = 1; i <= m; ++i) cin >> x[i] >> y[i] >> w[i];
		cin >> q;
		for(int i = 1; i <= q; ++i) queri[i].read();
		if (subtask1::check()) return subtask1::main_code() , 0;
		if (subtask2::check()) return subtask2::main_code() , 0;
		if (subtask3::check()) return subtask3::main_code() , 0;
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:188:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:189:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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