Submission #673799

#	Time	Username	Problem	Language	Result	Execution time	Memory
673799		QwertyPi	Bridges (APIO19_bridges)	C++14	0 / 100	3054 ms	70532 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second

const int B = 400;
const int N = 5e4 + 11;
const int M = 1e5 + 11;
using namespace std;

struct DSU{
	vector<pair<int, int>> hist;
	int dsu[N], sz[N];
	void init(int n) { for(int i = 0; i <= n; i++) dsu[i] = i, sz[i] = 1; }
	int f(int x) { return x == dsu[x] ? x : f(dsu[x]); }
	int get_size(int x) { return sz[f(x)]; }
	void g(int x, int y) { 
		x = f(x), y = f(y); 
		if(x == y) { hist.push_back({-1, -1}); return; } 
		if(sz[x] < sz[y]) swap(x, y); 
		sz[x] += sz[y]; dsu[y] = x;
		hist.push_back({x, y});
	}
	void back(){
		pair<int, int> p = hist.back(); hist.pop_back();
		if(p.fi == -1) return;
		sz[p.fi] -= sz[p.se];
		dsu[p.se] = p.se;
	}
} dsu;

vector<pair<int, int>> vp;
int w[M];

struct query{
	int t, a, b, ans;
};

struct edge{
	int u, v, w;
};

struct range{
	int l, r, e;
};

vector<query> Q;
vector<edge> E;

void add_edge(int m){
	E.clear();
	for(int i = 0; i < m; i++){
		E.push_back({vp[i].fi, vp[i].se, w[i]});
	}
	sort(E.begin(), E.end(), [](edge a, edge b){
		return a.w < b.w;
	});
}

vector<int> T[N << 2];
void add(int t, int l, int r, int ql, int qr, int qv){
	if(r < ql || qr < l) return;
	if(ql <= l && r <= qr) {
		T[t].push_back(qv);
		return;
	}
	int m = (l + r) / 2;
	add(t << 1, l, m, ql, qr, qv);
	add(t << 1 | 1, m + 1, r, ql, qr, qv); 
}

vector<int> ans;
vector<int> t1; vector<pair<int, int>> t2;
int n, m; 
void dfs(int t, int l, int r){
	for(auto i : T[t]){
		dsu.g(vp[i].fi, vp[i].se);
	}
	if(l == r){
		if(l < t2.size()){
			int a = dsu.get_size(Q[t2[l].fi].a);
			ans.push_back(a);
		}
	}else{
		int m = (l + r) / 2;
		dfs(t << 1, l, m);
		dfs(t << 1 | 1, m + 1, r);
	}
	for(auto i : T[t]){
		dsu.back();
	}
}

int main(){
	cin >> n >> m;
	vp.push_back({});
	for(int i = 1; i <= m; i++){
		int u, v, _w;
		cin >> u >> v >> _w;
		vp.push_back({u, v});
		w[i] = _w;
	}
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int t, a, b;
		cin >> t >> a >> b;
		Q.push_back({t, a, b});
	}
	
	for(int i = 0; i < q; i += B){
		add_edge(m); dsu.init(n);
		t1.clear(); t2.clear();
		int id_t2 = 0;
		for(int j = i; j < min(q, i + B); j++){
			if(Q[j].t == 1) t1.push_back(j);
			else t2.push_back({j, id_t2++});
		}
		bool u[M] = {}; int spi[M] = {}, w[M] = {}; for(int j = 1; j <= m; j++) w[j] = ::w[j];
		vector<int> sp; for(int j = 0; j < t1.size(); j++) sp.push_back(Q[t1[j]].a), spi[Q[t1[j]].a] = j, u[Q[t1[j]].a] = true;
		sort(sp.begin(), sp.end()); sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
		vector<range> ranges;
		int id = 0;
		for(int k = 0; k < t2.size(); k++){
			while(id < t1.size() && t1[id] < t2[k].fi) w[Q[t1[id]].a] = Q[t1[id]].b, id++;
			for(int j = 0; j < sp.size(); j++){
				if(w[sp[j]] >= Q[t2[k].fi].b){
					ranges.push_back({k, k, sp[j]});
				}
			}
		}
		sort(t2.begin(), t2.end(), [](pair<int, int> x, pair<int, int> y){
			return Q[x.fi].b > Q[y.fi].b;
		});
		int mp[B];
		for(int i = 0; i < t2.size(); i++) mp[t2[i].se] = i;
		for(auto r : ranges){
			add(1, 0, B, mp[r.l], mp[r.r], r.e);
		}
		for(int j = 1; j <= m; j++){
			if(u[j]) continue;
			int l = 0, r = (int) t2.size();
			while(l != r){
				int m = (l + r) / 2;
				if(Q[t2[m].fi].b > ::w[j]){
					l = m + 1;
				}else{
					r = m;
				}
			}
			add(1, 0, B, l, B, j);
		}
		ans.clear();
		dfs(1, 0, B - 1);
		for(int j = 0; j < t2.size(); j++){
			Q[t2[j].fi].ans = ans[j];
		}
		for(int j = i; j < min(q, i + B); j++){
			if(Q[j].t == 1){
				w[Q[j].a] = Q[j].b;
			}
		}
	}
	for(int i = 0; i < q; i++){
		if(Q[i].t == 2){
			cout << Q[i].ans << endl;
		}
	}
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(int, int, int)':
bridges.cpp:79:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if(l < t2.size()){
      |      ~~^~~~~~~~~~~
bridges.cpp:88:11: warning: unused variable 'i' [-Wunused-variable]
   88 |  for(auto i : T[t]){
      |           ^
bridges.cpp: In function 'int main()':
bridges.cpp:118:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   vector<int> sp; for(int j = 0; j < t1.size(); j++) sp.push_back(Q[t1[j]].a), spi[Q[t1[j]].a] = j, u[Q[t1[j]].a] = true;
      |                                  ~~^~~~~~~~~~~
bridges.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for(int k = 0; k < t2.size(); k++){
      |                  ~~^~~~~~~~~~~
bridges.cpp:123:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    while(id < t1.size() && t1[id] < t2[k].fi) w[Q[t1[id]].a] = Q[t1[id]].b, id++;
      |          ~~~^~~~~~~~~~~
bridges.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    for(int j = 0; j < sp.size(); j++){
      |                   ~~^~~~~~~~~~~
bridges.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for(int i = 0; i < t2.size(); i++) mp[t2[i].se] = i;
      |                  ~~^~~~~~~~~~~
bridges.cpp:153:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   for(int j = 0; j < t2.size(); j++){
      |                  ~~^~~~~~~~~~~
bridges.cpp:117:23: warning: variable 'spi' set but not used [-Wunused-but-set-variable]
  117 |   bool u[M] = {}; int spi[M] = {}, w[M] = {}; for(int j = 1; j <= m; j++) w[j] = ::w[j];
      |                       ^~~

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