Submission #905934

#	Time	Username	Problem	Language	Result	Execution time	Memory
905934		Boycl07	Bridges (APIO19_bridges)	C++17	100 / 100	2831 ms	10592 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}


const int N =  1e5 + 10;
const int M = 1e3 + 3;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const ll LINF = 1e17 + 2;
const int block_size = 500;
const int LOG = 29;
const int offset = N;
const int LIM = 1e4 ;
const int AL = 26;

int n, m, q;
const int S = 400;


struct Dsu_rollback
{
	int par[N], sz[N];
	int cur = 0;


	pii st[2 * N];

	void init(int n_)
	{
		rep(i, n_) par[i] = i, sz[i] = 1;
		cur = 0;
	}

	int find_set(int u)
	{
		while(u != par[u]) u = par[u]; return u;
	}

	void union_set(int u, int v)
	{
		if((u = find_set(u)) == (v = find_set(v))) return;
		st[++cur] = {u, sz[u]};
		st[++cur] = {v, sz[v]};

		if(sz[u] < sz[v]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
	}

	void roll_back(int lst)
	{
		while(cur > lst)
		{
			int u = st[cur].fi, sz_u = st[cur].se;
			par[u] = u;
			sz[u] = sz_u;
			--cur;
		}
	}
} dsu;

bool ch[N];

vector<int> unchanged_edges;
vector<int> changed_edges;
vector<int> queries;

vector<int> g[S + 2];

int u[N], v[N], w[N];
int t[N], x[N], y[N];

int ans[N];

void solve()
{
    cin >> n >> m;
	rep(i, m) cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	rep(i, q) cin >> t[i] >> x[i] >> y[i];

	for(int l = 1; l <= q; l += S)
	{
		dsu.init(n);
		changed_edges.clear();
		unchanged_edges.clear();
		queries.clear();
		int r = min(l + S - 1, q);
		rep(i, m) ch[i] = 0;
		forn(i, l, r)
		{
			if(t[i] == 1) ch[x[i]] = 1;
			else
				queries.pb(i);
			g[i - l].clear();
		}
		rep(i, m) if(ch[i]) changed_edges.pb(i);
		else unchanged_edges.pb(i);

		sort(all(unchanged_edges), [] (const int &a, const int &b) {
			return w[a] > w[b];
		});
		sort(all(queries), [] (const int &a, const int &b) {
			return y[a] > y[b];
		});


		forn(i, l, r)
			if(t[i] == 1)
				w[x[i]] = y[i];
			else
				for(int j : changed_edges)
					if(w[j] >= y[i])
						g[i - l].pb(j);
		int j = 0;
		for(int i : queries)
		{
			while(j < sz(unchanged_edges) && w[unchanged_edges[j]] >= y[i])
			{
				int idx = unchanged_edges[j];
				dsu.union_set(u[idx], v[idx]);
				++j;
			}

			int lst = dsu.cur;

			for(int t : g[i - l])
				dsu.union_set(u[t], v[t]);

			ans[i] = dsu.sz[dsu.find_set(x[i])];

			dsu.roll_back(lst);
		}
	} 
	rep(i, q) if(t[i] == 2) cout << ans[i] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;


    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}
//ha

Compilation message (stderr)

bridges.cpp: In member function 'int Dsu_rollback::find_set(int)':
bridges.cpp:64:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   64 |   while(u != par[u]) u = par[u]; return u;
      |   ^~~~~
bridges.cpp:64:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   64 |   while(u != par[u]) u = par[u]; return u;
      |                                  ^~~~~~

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