제출 #121425

#제출 시각아이디문제언어결과실행 시간메모리
121425abacaba다리 (APIO19_bridges)C++17
73 / 100
3018 ms13976 KiB
#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 e first
#define w 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, ind;
	bool operator < (const edge &b) const {
		if(w == b.w)
			return ind > b.ind;
		return w > b.w;
	}
};

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

const int block = 515;
const int N = 1e5 + 1;
int n, m, q, ans[N], p[N], sz[N], szupd, szqq;
vector <int> g[N];
set <edge> edges;
vector <int> was;
edge last[N], back[N];
query qq[N];
pii upd[N];
edge e[N];
bool used[N], usedupd[N], start[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);
}

int c;

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];
		e[i].ind = i;
		edges.insert(e[i]);
	}
	scanf("%d", &q);
	for(int i = block - 1; i <= q; i += block)
		start[i] = true;
	for(int i = 1; i <= q; ++i) {
		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;
		}
		if(start[i]) {
			sort(qq, qq + szqq);
			for(int i = 0; i < szupd; ++i)
				edges.erase(e[upd[i].e]);
			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(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;
						int a = find(x.u), b = find(x.v);
						if(x.w >= cur.w && a != b) {
							g[a].pb(b);
							g[b].pb(a);
						}
					}
					usedupd[upd[i].e] = true;
				}
				for(int i = cur.updatesTillNow; i < szupd; ++i) {
					if(!usedupd[upd[i].e]) {
						edge x = back[i];
						int a = find(x.u), b = find(x.v);
						if(x.w >= cur.w && a != b) {
							g[a].pb(b);
							g[b].pb(a);
						}
					}
					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;
					g[find(e[upd[i].e].u)].clear();
					g[find(e[upd[i].e].v)].clear();
				}

				while(!was.empty()) {
					used[was.back()] = false;
					was.ppb();
				}
			}
			for(int i = 0; i < szupd; ++i) {
				edges.erase(e[upd[i].e]);
				e[upd[i].e].w = upd[i].w;
				edges.insert(e[upd[i].e]);
			}
			szqq = szupd = 0; 
		}
	}
	sort(qq, qq + szqq);
	for(int i = 0; i < szupd; ++i)
		edges.erase(e[upd[i].e]);
	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(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;
				int a = find(x.u), b = find(x.v);
				if(x.w >= cur.w && a != b) {
					g[a].pb(b);
					g[b].pb(a);
				}
			}
			usedupd[upd[i].e] = true;
		}
		for(int i = cur.updatesTillNow; i < szupd; ++i) {
			if(!usedupd[upd[i].e]) {
				edge x = back[i];
				int a = find(x.u), b = find(x.v);
				if(x.w >= cur.w && a != b) {
					g[a].pb(b);
					g[b].pb(a);
				}
			}
			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;
			g[find(e[upd[i].e].u)].clear();
			g[find(e[upd[i].e].v)].clear();
		}

		while(!was.empty()) {
			used[was.back()] = false;
			was.ppb();
		}
	}
	for(int i = 0; i < szupd; ++i) {
		edges.erase(e[upd[i].e]);
		e[upd[i].e].w = upd[i].w;
		edges.insert(e[upd[i].e]);
	}
	szqq = szupd = 0; 
	for(int i = 1; i <= q; ++i)
		if(ans[i])
			printf("%d\n", ans[i]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:81: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:83: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:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
bridges.cpp:94: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:101: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);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...