oj.uz

Submission #209499

# Submission time Handle Problem Language Result Execution time Memory
209499 2020-03-14T11:57:37 Z mieszko11b Bridges (APIO19_bridges) C++14
0 / 100
 2795 ms 23220 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

const int SQRT = 600;

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];
int maxv;
vector<int> not_changed[200007];

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> 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);
	}
	for(int j = 0 ; j < maxv ; j++)
		not_changed[j].clear();
	for(int i = 1 ; i <= m ; i++) {
		if(!changed[i])
			not_changed[c[i]].push_back(i);
		else
			chacha.push_back(i);
	}
	sort(Q.begin(), Q.end(), greater<ii>());
	
	DSU *dsu = new DSU(n);
	
	int v = maxv;
	for(int j = 0 ; j < Q.size() ; j++) {
		int q = Q[j].Y;
		
		for(int i = e[q] ; i < v ; i++)
			for(int e : not_changed[i])
				dsu->Union(a[e], b[e]);
		v = e[q];
				
		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]);
	}

	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);
	
	vector<int> hlp;
	
	for(int i = 1 ; i <= m ; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		hlp.push_back(c[i]);
	}
	scanf("%d", &q);
	for(int i = 1 ; i <= q ; i++) {
		scanf("%d%d%d", &t[i], &d[i], &e[i]);
		hlp.push_back(e[i]);
	}
		
	sort(hlp.begin(), hlp.end());
	hlp.resize(distance(hlp.begin(), unique(hlp.begin(), hlp.end())));
	map<int, int> M;
	for(int i = 0 ; i < hlp.size() ; i++)
		M[hlp[i]] = i;
	maxv = hlp.size() - 1;
	for(int i = 1 ; i <= m ; i++)
		c[i] = M[c[i]];
	for(int i = 1 ; i <= q ; i++)
		e[i] = M[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

bridges.cpp: In function 'void process_queries(int, int)':
bridges.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < Q.size() ; j++) {
                  ~~^~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < hlp.size() ; i++)
                  ~~^~~~~~~~~~~~
bridges.cpp:143: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:148: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:151:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:153: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2236 ms 19928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1671 ms 17688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2795 ms 23220 KB Output is correct
2 Correct 174 ms 12012 KB Output is correct
3 Incorrect 259 ms 15216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2236 ms 19928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -