Submission #121347

#	Time	Username	Problem	Language	Result	Execution time	Memory
121347		abacaba	Bridges (APIO19_bridges)	C++14	13 / 100	3038 ms	13228 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>

const int inf = 2e9;
const int block = 320;
const int N = 1e5 + 15;
int n, m, q, ans[N], p[N], sz[N];

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

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

edge e[N];
query qs[N];

int updatesCnt, update[N];
bool used[N];
vector <int> updates;

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];
	}
}

vector <pii> g[N];
vector <query> qq, upd;
set <edge> edges;
vector <int> was;
edge last[N], back[N];

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

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

bool usedupd[N];

inline void solve() {
	edges.clear();
	sort(qq.begin(), qq.end());
	getrid();
	set <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(query cur : qq) {
		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;
				g[find(x.u)].pb(mp(find(x.v), x.w));
				g[find(x.v)].pb(mp(find(x.u), x.w));
			}
			usedupd[upd[i].e] = true;
		}
		for(int i = cur.updatesTillNow; i < upd.size(); ++i) {
			if(!usedupd[upd[i].e]) {
				edge x = back[i];
				g[find(x.u)].pb(mp(find(x.v), x.w));
				g[find(x.v)].pb(mp(find(x.u), x.w));
			}
			usedupd[upd[i].e] = true;
		}

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

		for(int i = 0; i < upd.size(); ++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];
				g[find(x.u)].ppb();
				g[find(x.v)].ppb();
			}
			usedupd[upd[i].e] = true;
		}
		for(int i = cur.updatesTillNow; i < upd.size(); ++i) {
			if(!usedupd[upd[i].e]) {
				edge x = back[i];
				g[find(x.u)].ppb();
				g[find(x.v)].ppb();
			}
			usedupd[upd[i].e] = true;
		}

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

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

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);
		e[i].ind = i;
		last[i] = e[i];
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) {
		scanf("%d", &qs[i].type);
		qs[i].ind = i;
		if(qs[i].type == 1) {
			scanf("%d%d", &qs[i].e, &qs[i].w);
			back[upd.size()] = last[qs[i].e];
			last[qs[i].e] = e[qs[i].e];
			last[qs[i].e].w = qs[i].w;
			upd.pb(qs[i]);
		}
		else {
			scanf("%d%d", &qs[i].v, &qs[i].w);
			qs[i].updatesTillNow = upd.size();
			qq.pb(qs[i]);
		}
		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 'void solve()':
bridges.cpp:123:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = cur.updatesTillNow; i < upd.size(); ++i) {
                                   ~~^~~~~~~~~~~~
bridges.cpp:134:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < upd.size(); ++i)
                  ~~^~~~~~~~~~~~
bridges.cpp:145:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = cur.updatesTillNow; i < upd.size(); ++i) {
                                   ~~^~~~~~~~~~~~
bridges.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < upd.size(); ++i)
                  ~~^~~~~~~~~~~~
bridges.cpp:162:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < upd.size(); ++i)
                 ~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:169: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:171: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:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &qs[i].type);
   ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:180:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &qs[i].e, &qs[i].w);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:187:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &qs[i].v, &qs[i].w);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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