Submission #409840

#	Time	Username	Problem	Language	Result	Execution time	Memory
409840		amunduzbaev	Bridges (APIO19_bridges)	C++14	100 / 100	2817 ms	10308 KiB

bridges

/* made by amunduzbaev */
 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"
 
using namespace std;
//using namespace __gnu_pbds;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
//#define int long long
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
template<int sz> using tut = array<int, sz>;
 
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//template<class T> using oset = tree<T, 
//null_type, less_equal<T>, rb_tree_tag, 
//tree_order_statistics_node_update> ordered_set;
 
const int N = 1e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
const int B = 500;
 
#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int w[N], par[N], sz[N], used[N], rr[N], ban[N];
tut<3> edges[N], qq[N];
vii last;
 
int f(int x) { return (x == par[x] ? x : f(par[x])); }
bool merge(int a, int b){
	a = f(a), b = f(b);
	if(a == b) return 0;
	if(sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b], par[b] = a;
	last.pb(b); return 1;
}

int ff(int x) { return (x == par[x] ? x : par[x] = ff(par[x])); }
void fmerge(int a, int b){
	a = f(a), b = f(b);
	if(a == b) return;
	if(sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b], par[b] = a;
}
 
void solve(int t_case){
	set<pii> ss;
	cin>>n>>m;
	for(int i=0;i<m;i++) cin>>edges[i][0]>>edges[i][1]>>edges[i][2];
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>qq[i][0]>>qq[i][1]>>qq[i][2];
		if(qq[i][0] == 1) qq[i][1]--;
	} for(int i=0;i<m;i++) ss.insert({edges[i][2], i});
	
	
	for(int i=0;i<B;i++){
		int l = i * B, r = min(q, (i + 1) * B);
		if(l >= r) break;
		vector<tut<3>> tt;
		stack<pii> ed;
		for(int j=l;j<r;j++){
			if(qq[j][0] == 1) ban[qq[j][1]] = 1;
			else tt.pb({qq[j][2], qq[j][1], j});
		} sort(rall(tt));
		for(int j=1;j<=n;j++) par[j] = j, sz[j] = 1;
		for(auto x : ss) if(!ban[x.ss]) ed.push(x);
		for(int j=0;j<sz(tt);j++){
			while(!ed.empty() && ed.top().ff >= tt[j][0])
				fmerge(edges[ed.top().ss][0], edges[ed.top().ss][1]), ed.pop();
			stack<int> bad;
			for(int in = tt[j][2]; in >= l; in--){
				if(qq[in][0] == 1 && !used[qq[in][1]]){
					if(qq[in][2] >= tt[j][0]) merge(edges[qq[in][1]][0], edges[qq[in][1]][1]);
					used[qq[in][1]] = 1, bad.push(qq[in][1]);
				}
			} for(int in = tt[j][2]; in < r; in++){
				if(qq[in][0] == 1 && !used[qq[in][1]]){
					if(edges[qq[in][1]][2] >= tt[j][0]) merge(edges[qq[in][1]][0], edges[qq[in][1]][1]);
					used[qq[in][1]] = 1, bad.push(qq[in][1]);
				}
			} rr[tt[j][2]] = sz[f(tt[j][1])]; 
			while(!last.empty()){
				int b = last.back();
				sz[par[b]] -= sz[b], par[b] = b; 
				last.pop_back();
			} while(!bad.empty()) used[bad.top()] = 0, bad.pop();
		} for(int j=l;j<r;j++) if(qq[j][0] == 1){ ban[qq[j][1]] = 0;
			ss.erase({edges[qq[j][1]][2], qq[j][1]});
			edges[qq[j][1]][2] = qq[j][2];
			ss.insert({edges[qq[j][1]][2], qq[j][1]});
		}
	} 
	for(int i=0;i<q;i++) if(qq[i][0] == 2) cout<<rr[i]<<"\n";
}
 
signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void usaco(std::string)':
bridges.cpp:32:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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