oj.uz

Submission #255140

# Submission time Handle Problem Language Result Execution time Memory
255140 2020-07-31T10:29:21 Z Atalasion Bridges (APIO19_bridges) C++14
0 / 100
 3000 ms 13680 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
const int SQ = 110;
struct tagh{
	int v, SZ;
};
vector<tagh> Ch;

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

vi Yal[N];
int n, m, q, W[N], E[N], V[N], U[N], par[N], sz[N], w[N], ans[N], mark[N], mark2[N], ww[N];
vector<query> L[N];
pair<int, pii> Q[N];

bool cmp(int x, int y){
	return W[x] > W[y];
}

int getpar(int v){
	return (par[v] == v?v:getpar(par[v]));
}

inline void merge(int v, int u){
	v = getpar(v), u = getpar(u);
	if (v == u) return;
	if (sz[v] < sz[u]) swap(v, u);
	tagh res;
	res.v = u;
	res.SZ = sz[u];
	Ch.pb(res);
	res.v = v;
	res.SZ = sz[v];
	Ch.pb(res);
	sz[v] += sz[u];
	par[u] = v;

}

inline void Solve(query q, int l, int r){
	vector<int> edge;
	for (int i = q.id; i >= l; i--){
		if (Q[i].F == 1){
			if (!mark2[Q[i].S.F]){
				w[Q[i].S.F] = Q[i].S.S, mark2[Q[i].S.F] = 1;
				if (w[Q[i].S.F] >= q.w) edge.pb(Q[i].S.F);
			}
		}
	}
	for (int i = q.id; i < r; i++){
		if (Q[i].F == 1){
			if (!mark2[Q[i].S.F]){
				mark2[Q[i].S.F] = 1;
				if (W[Q[i].S.F] >= q.w) edge.pb(Q[i].S.F);
			}
		}
	}
	Ch.clear();
	for (int i = l; i <= r; i++) mark2[Q[i].S.F] = 0;
	for (auto u:edge){
		merge(V[u], U[u]);
	}
	ans[q.id] = sz[getpar(q.v)];
	reverse(all(Ch));
	for (auto u:Ch){
		par[u.v] = u.v;
		sz[u.v] = u.SZ;
	}
	Ch.clear();
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int v,u, w;
		cin >> v >> u >> w;
		E[i] = i;
		W[i] = w;
		V[i] = v;
		U[i] = u;
	}
	sort(E + 1, E + m + 1, cmp);
	cin >> q;
	set<pii> st;
	vi num;
	for (int i = 0; i <q; i++){
		int t, v, u;
		cin >> t >> v >> u;
		Q[i] = {t, {v, u}};
		num.pb(u);
	}
	sort(all(num));
	num.resize(unique(all(num)) - num.begin());
	for (int i = 1; i <= m; i++){
		int koj = upper_bound(all(num), W[i]) - num.begin();
		W[i] = koj;
	}
	for (int i = 0; i< q; i++){
		memset(mark, 0, sizeof mark);
		for (int j = 0; j <= q; j++) Yal[j].clear();
		for (int j = 1; j <= m; j++) Yal[W[j]].pb(j);
		if (i * SQ >= q) break;
		for (int j = 0; j <= m; j++) L[j].clear(), L[j].shrink_to_fit();
		for (int j = i * SQ; j < min(q, (i + 1) * SQ); j++){
			int t = Q[j].F, v = Q[j].S.F, u = Q[j].S.S;
			int koj = lower_bound(all(num), u) - num.begin() + 1;
			Q[j].S.S = koj;
			u = koj;
			if (t == 2){
				query q;
				q.id = j;
				q.v = v;
				q.w = u;
				L[koj].pb(q);
//				cout << l << '\n';
			}else{
				mark[v] = 1;
			}
		}
		for (int j = 1; j <= n; j++) par[j] = j, sz[j] = 1;
		for (int j = q; j >= 0; j--){
			for (auto u:Yal[j]){
				if (!mark[u]) merge(V[u], U[u]);
			}
			for (auto u:L[j]){
				Solve(u, i * SQ, min(q, (i + 1) * SQ));
			}
		}
		for (int j = i * SQ; j < min(q, (i + 1) * SQ); j++) if(Q[j].F == 1){
			W[Q[j].S.F] = Q[j].S.S;
		}
	}
	for (int i = 0; i < q; i++){
		if (Q[i].F == 2) cout << ans[i] << '\n';
	}







	return 0;
}

/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
5
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5504 KB Output is correct
2 Correct 5 ms 5504 KB Output is correct
3 Incorrect 2107 ms 6508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 11632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 10512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 13680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 11632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5504 KB Output is correct
2 Correct 5 ms 5504 KB Output is correct
3 Incorrect 2107 ms 6508 KB Output isn't correct
4 Halted 0 ms 0 KB -