Submission #258291

#	Time	Username	Problem	Language	Result	Execution time	Memory
258291		amoo_safar	Bridges (APIO19_bridges)	C++14	100 / 100	2945 ms	122788 KiB

bridges

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const int N = 1e5 + 10;
const int Sq = 700;

int n, m, q, un;
int fr[N], to[N], w[N];
int t[N], a[N], b[N], ans[N];

int mk[N], Tmk = 1;
int mk2[N], Tmk2 = 1;

int par[N], sz[N];
inline int Find(int u){
	if(par[u] == u) return u;
	int w, v = u;
	while(par[u] != u) u = par[u];
	while(v != u){
		w = v;
		v = par[v];
		par[w] = u;
	}
	return u;
}
inline void Unite(int u, int v){
	u = Find(u); v = Find(v);
	if(u == v) return ;
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
}

vector<int> Ws[N];

vector<int> E[N], Q[N], G[N];

int que[N], lq, rq;

void Solve(int l, int r){

	iota(par, par + n + 1, 0);
	fill(sz, sz + n + 1, 1);
	for(int i = 0; i < un; i++) E[i].clear();
	for(int i = 0; i < un; i++) Q[i].clear();
	Tmk ++;
	//////////////////
	for(int i = l; i < r; i++)
		if(t[i] == 1) mk[a[i]] = Tmk;

	for(int i = 1; i <= m; i++) if(mk[i] != Tmk) E[w[i]].pb(i);
	vector<int> C;
	for(int i = 1; i <= m; i++) if(mk[i] == Tmk) C.pb(i);

	for(int i = l; i < r; i++){
		if(t[i] == 1){
			w[a[i]] = b[i];
		}
		if(t[i] == 2){
			for(auto &x : C) Ws[i].pb(w[x]);
			Q[b[i]].pb(i);
		}
	}

	int ed;
	for(int W = un; W >= 0; W--){
		for(auto &x : E[W]) Unite(fr[x], to[x]);
		for(auto &id : Q[W]){

			for(int i = 0; i < (int) C.size(); i++){
				if(Ws[id][i] < W) continue;
				ed = C[i];
				G[Find(fr[ed])].pb(Find(to[ed]));
				G[Find(to[ed])].pb(Find(fr[ed]));
			}

			Tmk2 ++;

			lq = 0, rq = 1;
			que[0] = Find(a[id]);
			mk2[que[0]] = Tmk2;
			while(lq < rq){
				ans[id] += sz[que[lq]];

				for(auto &adj : G[que[lq]]){
					if(mk2[adj] != Tmk2){
						mk2[adj] = Tmk2;
						que[rq ++] = adj;
					}
				}
				lq ++;
			}
			for(int i = 0; i < (int) C.size(); i++) G[ Find(fr[C[i]]) ].clear();
			for(int i = 0; i < (int) C.size(); i++) G[ Find(to[C[i]]) ].clear();
		}
	}

}

int main(){
	//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//cin >> n >> m;
	scanf("%d%d", &n, &m);
	vector<int> V;
	for(int i = 1; i <= m; i++){
		//cin >> fr[i] >> to[i] >> w[i];
		scanf("%d%d%d", fr + i, to + i, w + i);
		//V.pb(w[i]);
	}
	//cin >> q;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		scanf("%d%d%d", t + i, a + i, b + i);
		//cin >> t[i] >> a[i] >> b[i];
		if(t[i] == 2) V.pb(b[i]);	
	}
	V.pb(-1);
	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	for(int i = 1; i <= m; i++)
		w[i] = (upper_bound(all(V), w[i]) - V.begin()) - 1;
	for(int i = 1; i <= q; i++)
		b[i] = (upper_bound(all(V), b[i]) - V.begin()) - 1;

	un = V.size();

	for(int i = 1; i <= q; i += Sq)
		Solve(i, min(q + 1, i + Sq));
	
	for(int i = 1; i <= q; i++) if(t[i] == 2) printf("%d\n", ans[i]); //cout << ans[i] << '\n';
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:116: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:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", fr + i, to + i, w + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", t + i, a + i, b + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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