Submission #121354

#	Time	Username	Problem	Language	Result	Execution time	Memory
121354		abacaba	Bridges (APIO19_bridges)	C++14	59 / 100	3011 ms	7360 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

struct edge {
	int u, v, w;
	bool operator < (const edge &b) const {
		return w > b.w;
	}
};

struct update {
	int e, w;
};

struct query {
	int v, w, updatesTillNow, ind;
	bool operator < (const query &b) const {
		return w > b.w;
	}
};

const int inf = 2e9;
const int block = 320;
const int N = 1e5 + 15;
int n, m, q, ans[N], p[N], sz[N];
vector <int> g[N];
vector <edge> edges;
vector <int> was;
edge last[N], back[N];
query qq[N];
update upd[N];
int szupd, szqq;
edge e[N];
bool used[N], usedupd[N];

int find(int v) {
	if(v == p[v])
		return v;
	return p[v] = find(p[v]);
}

inline void unio(int a, int b) {
	a = find(a);
	b = find(b);
	if(a != b) {
		if(sz[a] < sz[b])
			swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
}


void dfs(int v, int ind, int w) {
	used[v] = true;
	was.pb(v);
	ans[ind] += sz[v];
	for(int to : g[v])
		if(!used[to])
			dfs(to, ind, w);
}

inline void getrid() {
	for(int i = 0; i < szupd; ++i)
		used[upd[i].e] = true;
	for(int i = 1; i <= m; ++i)
		if(!used[i])
			edges.pb(e[i]);
	for(int i = 0; i < szupd; ++i)
		used[upd[i].e] = false;
}


inline void solve() {
	edges.clear();
	sort(qq, qq + szqq);
	getrid();
	sort(edges.begin(), edges.end());
	vector <edge>::iterator it = edges.end();
	if(!edges.empty())
		it = edges.begin();
	for(int i = 1; i <= n; ++i)
		p[i] = i, sz[i] = 1;
	for(int k = 0; k < szqq; ++k) {
		query cur = qq[k];
		while(it != edges.end() && it->w >= cur.w) {
			unio(it->v, it->u);
			++it;
		}
		for(int i = cur.updatesTillNow - 1; i >= 0; --i) {
			if(!usedupd[upd[i].e]) {
				edge x = e[upd[i].e];
				x.w = upd[i].w;
				if(x.w >= cur.w && find(x.u) != find(x.v)) {
					g[find(x.u)].pb(find(x.v));
					g[find(x.v)].pb(find(x.u));
				}
			}
			usedupd[upd[i].e] = true;
		}
		for(int i = cur.updatesTillNow; i < szupd; ++i) {
			if(!usedupd[upd[i].e]) {
				edge x = back[i];
				if(x.w >= cur.w && find(x.u) != find(x.v)) {
					g[find(x.u)].pb(find(x.v));
					g[find(x.v)].pb(find(x.u));
				}
			}
			usedupd[upd[i].e] = true;
		}

		dfs(find(cur.v), cur.ind, cur.w);

		for(int i = 0; i < szupd; ++i)
			usedupd[upd[i].e] = false;

		for(int i = cur.updatesTillNow - 1; i >= 0; --i) {
			if(!usedupd[upd[i].e]) {
				edge x = e[upd[i].e];
				x.w = upd[i].w;
				if(x.w >= cur.w && find(x.u) != find(x.v)) {
					g[find(x.u)].ppb();
					g[find(x.v)].ppb();
				}
			}
			usedupd[upd[i].e] = true;
		}
		for(int i = cur.updatesTillNow; i < szupd; ++i) {
			if(!usedupd[upd[i].e]) {
				edge x = back[i];
				if(x.w >= cur.w && find(x.u) != find(x.v)) {
					g[find(x.u)].ppb();
					g[find(x.v)].ppb();
				}
			}
			usedupd[upd[i].e] = true;
		}

		for(int i = 0; i < szupd; ++i)
			usedupd[upd[i].e] = false;

		while(!was.empty()) {
			used[was.back()] = false;
			was.ppb();
		}
	}
	for(int i = 0; i < szupd; ++i)
		e[upd[i].e].w = upd[i].w;
	szqq = szupd = 0; 
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
		last[i] = e[i];
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) {
		int c;
		scanf("%d", &c);
		if(c == 1) {
			scanf("%d%d", &upd[szupd].e, &upd[szupd].w);
			back[szupd] = last[upd[szupd].e];
			last[upd[szupd].e] = e[upd[szupd].e];
			last[upd[szupd].e].w = upd[szupd].w;
			++szupd;
		}
		else {
			scanf("%d%d", &qq[szqq].v, &qq[szqq].w);
			qq[szqq].updatesTillNow = szupd;
			qq[szqq].ind = i;
			++szqq;
		}
		if(i % block == 0)
			solve();
	}
	solve();
	for(int i = 1; i <= q; ++i)
		if(ans[i])
			printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:172: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:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:177:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
bridges.cpp:182:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &upd[szupd].e, &upd[szupd].w);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:189:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &qq[szqq].v, &qq[szqq].w);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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