Submission #126728

#	Time	Username	Problem	Language	Result	Execution time	Memory
126728		roseanne_pcy	Bridges (APIO19_bridges)	C++14	13 / 100	3052 ms	6416 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;
const int maxs = 325;
const int lim = 320;
int n, m, q;
int a[maxn], b[maxn], w[maxn];
bool chang[maxn];

struct que
{
	int t, a, b, id;
	bool operator < (que other)
	{
		return b> other.b;
	}
};

que qq[maxn];

const int maxu = 5e4+5;

struct dsu
{
	int par[maxu], rnk[maxu], cc[maxu];
	struct hist
	{
		int u, rnku, ccu, v, rnkv, ccv;
		hist(int _u, int _rnku, int _ccu, int _v, int _rnkv, int _ccv)
		{
			u = _u;
			rnku = _rnku;
			ccu = _ccu;
			v = _v;
			rnkv = _rnkv;
			ccv = _ccv;
		}
	};
	stack<hist> roll;
	dsu(int n = 0)
	{
		for(int i = 1; i<= n; i++)
		{
			par[i] = i;
			rnk[i] = 0;
			cc[i] = 1;
		}
	}
	int findset(int x)
	{
		if(x == par[x]) return x;
		return findset(par[x]);
	}
	bool unite(int a, int b)
	{
		int u = findset(a), v = findset(b);
		if(u == v) return false; 
		if(rnk[u]> rnk[v]) swap(u, v);
		roll.push(hist(u, rnk[u], cc[u], v, rnk[v], cc[v]));
		par[u] = v;
		cc[v] += cc[u];
		if(rnk[u] == rnk[v]) rnk[v]++;
		return true;
	}
	void rollback()
	{
		hist k = roll.top(); roll.pop(); 
		par[k.u] = k.u;
		rnk[k.u] = k.rnku;
		cc[k.u] = k.ccu;
		par[k.v] = k.v;
		rnk[k.v] = k.rnkv;
		cc[k.v] = k.ccv;
	}
};

dsu foo;

bool cmp(int a, int b)
{
	return w[a]> w[b];
}

bool cmp2(que a, que b)
{
	return a.id< b.id;
}

int ans[maxn];

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i<= m; i++) scanf("%d %d %d", &a[i], &b[i], &w[i]);
	scanf("%d", &q);
	for(int i = 1; i<= q; i++)
	{
		scanf("%d %d %d", &qq[i].t, &qq[i].a, &qq[i].b);
		qq[i].id = i;
	}
	vector<int> edges;
	for(int i = 1; i<= m; i++) edges.pb(i);
	for(int i = 1; 1+(i-1)*lim<= q; i++)
	{
		int s = 1+(i-1)*lim;
		int t = min(lim*i, q);
		memset(chang, 0, sizeof chang);
		for(int j = s; j<= t; j++)
		{
			if(qq[j].t == 1)
			{
				chang[qq[j].a] = true;
			}
		}
		sort(edges.begin(), edges.end(), cmp);
		sort(qq+s, qq+t+1);
		int ptr = 0;
		foo = dsu(n);
		for(int j = s; j<= t; j++)
		{
			if(qq[j].t == 1) continue;
			while(ptr< m && w[edges[ptr]]>= qq[j].b)
			{
				if(chang[edges[ptr]])
				{
					ptr++;
					continue;
				}
				foo.unite(a[edges[ptr]], b[edges[ptr]]);
				// printf("unite %d %d\n", a[edges[ptr]], b[edges[ptr]]);
				ptr++;
			}
			// printf("answering query %d\n", qq[j].id);
			map<int, ii> mod;
			for(int k = s; k<= t; k++)
			{
				if(qq[k].t == 2) continue;
				mod[qq[k].a] = max(mod[qq[k].a], {0, w[qq[k].a]});
				if(qq[k].id> qq[j].id) continue;
				mod[qq[k].a] = max(mod[qq[k].a], {qq[k].id, qq[k].b});
			}
			int connt = 0;
			for(auto kk : mod)
			{
				if(kk.Y.Y>= qq[j].b)
				{
					connt += foo.unite(a[kk.X], b[kk.X]);
				}
			}
			ans[qq[j].id] = foo.cc[foo.findset(qq[j].a)];
			while(connt--) foo.rollback();
		}
		sort(qq+s, qq+t+1, cmp2);
		for(int j = s; j<= t; j++)
		{
			if(qq[j].t == 1)
			{
				w[qq[j].a] = qq[j].b;
			}
		}
	}
	for(int i = 1; i<= q; i++)
	{
		if(ans[i]) printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:101: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:102:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= m; i++) scanf("%d %d %d", &a[i], &b[i], &w[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &qq[i].t, &qq[i].a, &qq[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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