Submission #409602

#	Time	Username	Problem	Language	Result	Execution time	Memory
409602		amunduzbaev	Bridges (APIO19_bridges)	C++14	59 / 100	3047 ms	8652 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 = 450;

#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];
tut<3> edges[N], qq[N];
vii last;

int f(int x) { return (x == par[x] ? x : f(par[x])); }
void merge(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;
	last.pb(b);
}

int ff(int x) { return (x == par[x] ? x : par[x] = ff(par[x])); }
void fmerge(int a, int b){
	a = ff(a), b = ff(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;
	//scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++) cin>>edges[i][0]>>edges[i][1]>>edges[i][2]; // scanf("%d%d%d", &edges[i][0], &edges[i][1], &edges[i][2]); 
	cin>>q;
	//scanf("%d", &q);
	for(int i=0;i<q;i++){
		cin>>qq[i][0]>>qq[i][1]>>qq[i][2];
		//scanf("%d%d%d", &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;
		for(int j=l;j<r;j++){
			if(qq[j][0] == 1) ss.erase({edges[qq[j][1]][2], qq[j][1]});
			else tt.pb({qq[j][2], qq[j][1], j});
		} sort(rall(tt));
		int j = 0;
		for(int j=1;j<=n;j++) par[j] = j, sz[j] = 1;
		
		for(auto it = ss.rbegin(); it != ss.rend(); it++){
			pii x = *it;
			while(j < sz(tt) && tt[j][0] > x.ff){
				int in = tt[j][2];
				int bef = sz(last);
				while(in >= l){
					if(qq[in][0] == 2) { in--; continue; }
					if(used[qq[in][1]]) { in--; continue; }
					used[qq[in][1]] = 1;
					if(qq[in][2] >= tt[j][0]){
						int a = edges[qq[in][1]][0], b = edges[qq[in][1]][1];
						merge(a, b);
					} in--;
				} in = tt[j][2];
				while(in < r){
					if(qq[in][0] == 2) { in++; continue; }
					if(used[qq[in][1]]) { in++; continue; }
					used[qq[in][1]] = 1;
					if(edges[qq[in][1]][2] >= tt[j][0]){
						int a = edges[qq[in][1]][0], b = edges[qq[in][1]][1];
						merge(a, b);
					} in++;
				} rr[tt[j][2]] = sz[f(tt[j][1])]; 
				j++;
				while(sz(last) > bef){
					int b = last.back();
					sz[par[b]] -= sz[b], par[b] = b; last.pop_back();
				} for(int i=l;i<r;i++) if(qq[i][0] == 1) used[qq[i][1]] = 0;
			} int a = edges[x.ss][0], b = edges[x.ss][1];
			fmerge(a, b);
		} while(j < sz(tt)) {
			int in = tt[j][2];
			int bef = sz(last);
			while(in >= l){
				if(qq[in][0] == 2) { in--; continue; }
				if(used[qq[in][1]]) { in--; continue; }
				used[qq[in][1]] = 1;
				if(qq[in][2] >= tt[j][0]){
					int a = edges[qq[in][1]][0], b = edges[qq[in][1]][1];
					merge(a, b);
				} in--;
			} in = tt[j][2];
			while(in < r){
				if(qq[in][0] == 2) { in++; continue; }
				if(used[qq[in][1]]) { in++; continue; }
				used[qq[in][1]] = 1;
				if(edges[qq[in][1]][2] >= tt[j][0]){
					int a = edges[qq[in][1]][0], b = edges[qq[in][1]][1];
					merge(a, b);
				} in++;
			} rr[tt[j][2]] = sz[f(tt[j][1])]; 
			j++;
			while(sz(last) > bef){
				int b = last.back();
				sz[par[b]] -= sz[b], par[b] = b; last.pop_back();
			} for(int i=l;i<r;i++) if(qq[i][0] == 1) used[qq[i][1]] = 0;
		} for(int j=l;j<r;j++) if(qq[j][0] == 1) edges[qq[j][1]][2] = qq[j][2];
		for(int j=l;j<r;j++) 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"; // printf("%d\n", rr[i]); 
}

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: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27