Submission #409806

#TimeUsernameProblemLanguageResultExecution timeMemory
409806amunduzbaevBridges (APIO19_bridges)C++14
59 / 100
3010 ms9176 KiB
/* 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])); }
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;
	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;
		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;
		auto it = ss.rbegin();
		for(int j=0;j<sz(tt);j++){
			while(it != ss.rend() && it->ff >= tt[j][0]){
				if(!ban[it->ss]) fmerge(edges[it->ss][0], edges[it->ss][1]);
				it++;
			} int in = tt[j][2];
			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])]; 
			while(sz(last)){
				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) ss.erase({edges[qq[j][1]][2], qq[j][1]}), ban[qq[j][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++) if(qq[j][0] == 1) 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 }
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...