Submission #209039

#	Time	Username	Problem	Language	Result	Execution time	Memory
209039		jtnydv25	Bridges (APIO19_bridges)	C++14	100 / 100	2992 ms	11532 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
	
#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double
	
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}
	
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}
	
#ifdef LOCAL
#define cerr cout
#else
#endif
	
#define TRACE
	
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int MASK = (1 << 30) - 1;
struct rollback_array{
	stack<ll> changes;
	vector<int> arr;
	int n;
	rollback_array(){n = 0;}
	rollback_array(int n) : n(n), arr(n){};
	void setall(int x){
		for(int i = 0; i < n; i++) arr[i] = x;
	}
	// if not to be rolled back just do arr[x] = v
	int & operator [] (int x){ return arr[x];}
	inline void update(int i, int v){
		changes.push((((ll)i) << 30) + arr[i]);
		arr[i] = v;
	}
	inline void click(){
		changes.push(-1);
	}
	inline void roll_back(){
		while(!changes.empty()){
			ll it = changes.top();
			changes.pop();
			if(it == -1) return;
			arr[it >> 30] = it & MASK;
		}
	}
};

struct rollback_dsu{
	int n;
	rollback_array par, num;
	rollback_dsu(int n) : n(n), par(n), num(n){
		par.setall(n);
		num.setall(1);
	}
	int root(int x){
		if(par[x] == n) return x;
		int rt = root(par[x]);
		par.update(x, rt);
		return rt;
	}
	void merge(int x, int y){
		x = root(x);
		y = root(y);
		if(x == y) return;
		if(num[x] > num[y]) swap(x, y);
		par.update(x, y);
		num.update(y, num[x] + num[y]);
	}
	void click(){
		par.click();
		num.click();
	}
	void roll_back(){
		par.roll_back();
		num.roll_back();
	}
};
	
const int N = 100005;
int a[N], b[N], w[2 * N];
int type[N], s[N];
bitset<N> changing;
const int BLOCK = 455;
int ans[N];
int temp[2 * N];
int cntr = 0;
int arr[N], sz_arr;
void go(vector<int> & b){
	int szb = sz(b);
	int pos_a = 0, pos_b = 0;
	cntr = 0;
	while(pos_a < sz_arr || pos_b < szb){
		if(pos_a < sz_arr && (pos_b == szb || w[arr[pos_a]] >= w[b[pos_b]])){
			temp[cntr++] = arr[pos_a++];
		}
		else{
			temp[cntr++] = b[pos_b++]; 
		}
	}
}
int which[BLOCK][BLOCK];
// bitset<BLOCK> which[BLOCK];
int main(){
	int n = 50000, m = 100000; 
	sd(n); sd(m);
	for(int i = 0; i < m; i++){
		// a[i] = rand() % n + 1; b[i] = rand() % n + 1; w[i] = rand() % 1000000;
		sd(a[i]); sd(b[i]); sd(w[i]);
		a[i]--; b[i]--;
	}
	int q = 100000; 
	sd(q);
	for(int i = 0; i < q; i++){
		// type[i] = rand() % 2 + 1;
		// if(type[i]==1) s[i] = rand() % m + 1;
		// else s[i] = rand() % n + 1;
		// w[i + m] = rand() % 1000000;
		sd(type[i]); sd(s[i]); sd(w[i + m]);
		s[i]--;
	}
	vector<int> perm(m); iota(all(perm), 0);
	sort(all(perm), [&](int i, int j){return w[i] > w[j];});
	rollback_dsu D(n);

	for(int i = 0; i * BLOCK < q; i++){
		int st = i * BLOCK, en = min(q - 1, st + BLOCK - 1);
		vector<int> queries;
		vector<int> changing_edges;
		changing.reset();
		for(int j = st; j <= en; j++){
			if(type[j] == 1){
				changing[s[j]] = 1;
			} else{
				queries.push_back(j + m);
			}
		}
		sz_arr = 0;
		for(int j = 0; j < m; j++){
			int ind = perm[j];
			if(changing[ind]){
				changing_edges.push_back(ind);
			} else{
				arr[sz_arr++] = ind;
			}
		}
		sort(all(queries), [&](int p, int q){return w[p] > w[q];});
		
		go(queries);
		D.click();
		for(int j = st; j <= en; j++){
			if(type[j] == 1){
				w[s[j]] = w[j + m];
			}else{
				for(int k = 0; k < sz(changing_edges); k++)
					which[j - st][k] = w[changing_edges[k]] >= w[j + m];
			}
		}

		for(int j = 0; j < cntr; j++){
			int ind = temp[j];
			if(ind < m){
				if(!changing[ind]){
					D.merge(a[ind], b[ind]);
				}
			} else{
				ind -= m;
				D.click();
				for(int k = 0; k < sz(changing_edges); k++) if(which[ind - st][k]){
					int e = changing_edges[k];
					D.merge(a[e], b[e]);
				}
				ans[ind] = D.num[D.root(s[ind])];
				D.roll_back();
			}
		}
		D.roll_back();
		sort(all(changing_edges), [&](int p, int q){return w[p] > w[q];});
		go(changing_edges);
		for(int j = 0; j < m; j++) perm[j] = temp[j];
	}

	for(int i = 0; i < q; i++) if(type[i] == 2) printf("%d\n", ans[i]);
}

Compilation message (stderr)

bridges.cpp: In constructor 'rollback_array::rollback_array(int)':
bridges.cpp:54:6: warning: 'rollback_array::n' will be initialized after [-Wreorder]
  int n;
      ^
bridges.cpp:53:14: warning:   'std::vector<int> rollback_array::arr' [-Wreorder]
  vector<int> arr;
              ^~~
bridges.cpp:56:2: warning:   when initialized here [-Wreorder]
  rollback_array(int n) : n(n), arr(n){};
  ^~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:136:2: note: in expansion of macro 'sd'
  sd(n); sd(m);
  ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:136:9: note: in expansion of macro 'sd'
  sd(n); sd(m);
         ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:139:3: note: in expansion of macro 'sd'
   sd(a[i]); sd(b[i]); sd(w[i]);
   ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:139:13: note: in expansion of macro 'sd'
   sd(a[i]); sd(b[i]); sd(w[i]);
             ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:139:23: note: in expansion of macro 'sd'
   sd(a[i]); sd(b[i]); sd(w[i]);
                       ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:143:2: note: in expansion of macro 'sd'
  sd(q);
  ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:149:3: note: in expansion of macro 'sd'
   sd(type[i]); sd(s[i]); sd(w[i + m]);
   ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:149:16: note: in expansion of macro 'sd'
   sd(type[i]); sd(s[i]); sd(w[i + m]);
                ^~
bridges.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
bridges.cpp:149:26: note: in expansion of macro 'sd'
   sd(type[i]); sd(s[i]); sd(w[i + m]);
                          ^~

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