Submission #209494

#	Time	Username	Problem	Language	Result	Execution time	Memory
209494		mieszko11b	Bridges (APIO19_bridges)	C++14	44 / 100	3097 ms	9360 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

const int SQRT = 1000;

int n, m;
int a[100007], b[100007], c[100007];
int q;
int t[100007], d[100007], e[100007], ans[100007];
bool changed[100007];
int lastw[100007];

struct DSU {
	int n;
	vector<int> p, rank;
	vector<vector<int>> G;
	int cnt;
	vector<bool> vis;
	vector<int> aff;
	
	DSU(int _n) {
		n = _n;
		p.resize(n + 1);
		rank.resize(n + 1);
		G.resize(n + 1);
		vis.resize(n + 1);
		for(int i = 1 ; i <= n ; i++) {
			p[i] = i;
			rank[i] = 1;
		}
	}
	
	int Find(int i) {
		if(p[i] == i)
			return i;
		return Find(p[i]);
	}
	
	void Union(int a, int b) {
		a = Find(a);
		b = Find(b);
		
		if(a == b)
			return ;
			
		if(rank[a] < rank[b]) {
			p[a] = b;
			rank[b] += rank[a];
		} else {
			p[b] = a;
			rank[a] += rank[b];
		}
	}
	
	void dfs(int w) {
		if(vis[w])
			return ;
		vis[w] = 1;
		aff.push_back(w);
		cnt += rank[w];
		for(int u : G[w])
			dfs(u);
	}
	
	int count(vector<int> &E, int w) {
		for(int e : E) {
			G[Find(a[e])].push_back(Find(b[e]));
			G[Find(b[e])].push_back(Find(a[e]));
		}
		cnt = 0;
		dfs(Find(w));
		for(int x : aff)
			vis[x] = 0;
		aff.clear();
		for(int e : E) {
			G[Find(a[e])].clear();
			G[Find(b[e])].clear();
		}
		return cnt;
	}
};


void process_queries(int x, int y) {
	vector<ii> not_changed, Q;
	vector<int> chacha;
	memset(changed, 0, sizeof changed);
	for(int i = x ; i <= y ; i++) {
		if(t[i] == 1)
			changed[d[i]] = 1;
		else
			Q.emplace_back(e[i], i);
	}
	not_changed.reserve(m);
	for(int i = 1 ; i <= m ; i++) {
		if(!changed[i])
			not_changed.push_back({c[i], i});
		else
			chacha.push_back(i);
	}
	sort(not_changed.begin(), not_changed.end(), greater<ii>());
	sort(Q.begin(), Q.end(), greater<ii>());
	
	DSU *dsu = new DSU(n);
	
	int i = 0, j = 0;
	while(i < not_changed.size() || j < Q.size()) {
		if(j == Q.size() || (i < not_changed.size() && not_changed[i].X >= Q[j].X)) {
			int e = not_changed[i].Y;
			dsu->Union(a[e], b[e]);
			i++;
		} else {
			int q = Q[j].Y;
			for(int e : chacha)
				lastw[e] = c[e];
			for(int k = x ; k < q ; k++)
				if(t[k] == 1)
					lastw[d[k]] = e[k];
			vector<int> E;
			for(int e : chacha)
				if(lastw[e] >= ::e[q])
					E.push_back(e);
			ans[q] = dsu->count(E, d[q]);
			j++;
		}
	}

	for(int k = x ; k <= y ; k++)
		if(t[k] == 1)
			c[d[k]] = e[k];	
			
	delete dsu;
}

int main() {
	scanf("%d%d",&n, &m);
	for(int i = 1 ; i <= m ; i++)
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	scanf("%d", &q);
	for(int i = 1 ; i <= q ; i++)
		scanf("%d%d%d", &t[i], &d[i], &e[i]);
		
	for(int i = 1 ; i <= q ; i += SQRT)
		process_queries(i, min(i + SQRT - 1, q));
		
	for(int i = 1 ; i <= q ; i++)
		if(ans[i])
			printf("%d\n", ans[i]);
		
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void process_queries(int, int)':
bridges.cpp:113:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < not_changed.size() || j < Q.size()) {
        ~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:113:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < not_changed.size() || j < Q.size()) {
                                  ~~^~~~~~~~~~
bridges.cpp:114:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j == Q.size() || (i < not_changed.size() && not_changed[i].X >= Q[j].X)) {
      ~~^~~~~~~~~~~
bridges.cpp:114:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j == Q.size() || (i < not_changed.size() && not_changed[i].X >= Q[j].X)) {
                        ~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n, &m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a[i], &b[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t[i], &d[i], &e[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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