Submission #169528

#	Time	Username	Problem	Language	Result	Execution time	Memory
169528		ZwariowanyMarcin	Bridges (APIO19_bridges)	C++14	100 / 100	2598 ms	26088 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;
	
const int nax = 1e5 + 111;
const int M = 400;

int n, m, q;

struct edge {
	int a, b, c;
};

edge e[nax];

struct gao {
	int l, r, a, b, c;
	gao () {}
	gao (int l, int r, int a, int b, int c) : l(l), r(r), a(a), b(b), c(c) {}
};

vector <gao> v;

int p[nax];
int t[nax][3];
int ans[nax];

struct uf {
	int p[nax];
	int ile[nax];
	
	void init() {
		for(int i = 1; i <= n; ++i) {
			p[i] = i;
			ile[i] = 1;
		}
	}
	int find(int x) {
		if(x == p[x])
			return x;
		return p[x] = find(p[x]);
	}
	void unia(int x, int y) {
		x = find(x);
		y = find(y);
		if(x != y) {
			p[x] = y;
			ile[y] += ile[x];
		}
	}
} ja;

struct qu {
	int v, w, id;
};

vector <gao> big;
vector <gao> small;
vector <qu> qq;

vector <int> graf[nax];

vector <int> nodes;
bool odw[nax];

void  dfs(int u) {
	nodes.pb(u);
	odw[u] = 1;
	for(auto it : graf[u])
		if(!odw[it])
			dfs(it);
}

void add(int a, int b) {
	graf[a].pb(b);
	graf[b].pb(a);
}

void del(int a, int b) {
	graf[a].pop_back();
	graf[b].pop_back();
}

void solve(int L, int R) {
	ja.init();
	qq.clear();
	small.clear();
	for(auto it : v) 
		if(!(it.r < L || R < it.l) && !(it.l <= L && R <= it.r))
			small.pb(it);
	
	for(int i = L; i <= R; ++i) 
		if(t[i][0] == 2)
			qq.pb({t[i][1], t[i][2], i});
			
	sort(qq.begin(), qq.end(), [](qu x, qu y) {
		return x.w < y.w;
	});
	
	int j = ss(big) - 1;
	for(int i = ss(qq) - 1; 0 <= i; --i) {
		qu on = qq[i];
		while(0 <= j && on.w <= big[j].c) {
			if(big[j].l <= L && R <= big[j].r)
				ja.unia(ja.find(big[j].a), ja.find(big[j].b));
			j--;
		}
		
		for(auto it : small) 
			if(it.l <= on.id && on.id <= it.r && on.w <= it.c) 
				add(ja.find(it.a), ja.find(it.b));
				
		nodes.clear();
		dfs(ja.find(on.v));
		
		for(auto it : nodes) {
			odw[it] = 0;
			ans[on.id] += ja.ile[it];
		}
		
		for(auto it : small)
			if(it.l <= on.id && on.id <= it.r && on.w <= it.c)
				del(ja.find(it.a), ja.find(it.b));
	}
}	
		
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) {
		scanf("%d %d %d", &t[i][0], &t[i][1], &t[i][2]);
		if(t[i][0] == 1) {
			v.pb(gao(p[t[i][1]], i - 1, e[t[i][1]].a, e[t[i][1]].b, e[t[i][1]].c));
			p[t[i][1]] = i;
			e[t[i][1]].c = t[i][2];
		}	
	}
	
	for(int i = 1; i <= m; ++i) 
		v.pb(gao(p[i], q, e[i].a, e[i].b, e[i].c));
		
	big = v;
	sort(big.begin(), big.end(), [](gao x, gao y) {
		return x.c < y.c;
	});
		
	for(int i = 1; i <= q; i += M) 
		solve(i, min(q, i + M - 1));
			
	for(int i = 1; i <= q; ++i) 
		if(t[i][0] == 2)
			printf("%d\n", ans[i]);
	
	
	
	
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:136: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:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t[i][0], &t[i][1], &t[i][2]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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