Submission #148076

#	Time	Username	Problem	Language	Result	Execution time	Memory
148076		WhipppedCream	Bridges (APIO19_bridges)	C++17	60 / 100	3041 ms	11744 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 lim = 800;
const int maxs = lim+5;
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 cap[maxn];
 
int st[4*maxn];
 
int ask(int i, int j, int p = 1, int L = 1, int R = n-1)
{
    if(i> R || j< L) return 1e9;
    if(i<= L && R<= j) return st[p];
    int M = (L+R)/2;
    int x = ask(i, j, 2*p, L, M);
    int y = ask(i, j, 2*p+1, M+1, R);
    return min(x, y);
}
 
void update(int x, int dx, int p = 1, int L = 1, int R = n-1)
{
    if(x> R || x< L) return;
    if(L == R)
    {
        st[p] = dx;
        return;
    }
    int M = (L+R)/2;
    update(x, dx, 2*p, L, M);
    update(x, dx, 2*p+1, M+1, R);
    st[p] = min(st[2*p], st[2*p+1]);
}
 
bool ok(int a, int b, int w)
{
	return w<= ask(a, b-1);
}
 
void st2()
{
	for(int i = 1; i<= m; i++)
	{
		update(i, w[i]);
	}
	scanf("%d", &q);
	while(q--)
	{
		int t; scanf("%d", &t);
		if(t == 1)
		{
			int id, c;
			scanf("%d %d", &id, &c);
			update(id, c);
		}
		else
		{
			int s, w; scanf("%d %d", &s, &w);
			int lo = 1, hi = s;
			while(lo< hi)
			{
				int mid = (lo+hi)/2;
				if(ok(mid, s, w)) hi = mid;
				else lo = mid+1;
			}
			int L = lo;
			lo = s, hi = n;
			while(lo< hi)
			{
				int mid = (lo+hi+1)/2;
				if(ok(s, mid, w)) lo = mid;
				else hi = mid-1;
			}
			int R = lo;
			printf("%d\n", R-L+1);
		}
	}
}
 
int deg[maxn];
 
void merge(vector<int> &res, vector<int> &A, vector<int> &B)
{
	res.clear();
	int n = A.size(), m = B.size();
	int i = 0, j = 0;
	while(i< n && j< m)
	{
		if(w[A[i]]> w[B[j]])
		{
			res.pb(A[i]);
			i++;
		}
		else
		{
			res.pb(B[j]);
			j++;
		}
	}
	while(i< n)
	{
		res.pb(A[i++]);
	}
	while(j< m)
	{
		res.pb(B[j++]);
	}
}
 
int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i<= m; i++)
	{
		scanf("%d %d %d", &a[i], &b[i], &w[i]);
		cap[i] = w[i];
		deg[a[i]]++; deg[b[i]]++;
	}
	int most = 0;
	for(int i = 1; i<= n; i++) most = max(most, deg[i]);
	if(most == 2 && m == n-1)
	{
		st2(); return 0;
	}
	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);
	sort(edges.begin(), edges.end(), cmp);
	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);
		vector<int> bad;
		for(int j = s; j<= t; j++)
		{
			if(qq[j].t == 1)
			{
				chang[qq[j].a] = true;
				bad.pb(qq[j].a);
			}
		}
		sort(bad.begin(), bad.end());
		bad.resize(unique(bad.begin(), bad.end())-bad.begin());
		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);
			vector< ii > mod(bad.size(), {0, 0});
			for(int k = s; k<= t; k++)
			{
				if(qq[k].t == 2) continue;
				int x = lower_bound(bad.begin(), bad.end(), qq[k].a)-bad.begin();
				mod[x] = max(mod[x], {0, w[qq[k].a]});
				if(qq[k].id> qq[j].id) continue;
				mod[x] = max(mod[x], {qq[k].id, qq[k].b});
			}
			int connt = 0;
			int run = 0;
			for(int u : bad)
			{
				if(mod[run++].Y>= qq[j].b)
				{
					connt += foo.unite(a[u], b[u]);
				}
			}
			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;
			}
		}
		vector<int> still, dyn;
		for(int e : edges)
		{
			if(chang[e])
			{
				dyn.pb(e);
			}
			else
			{
				still.pb(e);
			}
		}
		sort(dyn.begin(), dyn.end(), cmp);
		merge(edges, still, dyn);
	}
	for(int i = 1; i<= q; i++)
	{
		if(ans[i]) printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

bridges.cpp: In function 'void st2()':
bridges.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:142:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t);
          ~~~~~^~~~~~~~~~
bridges.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &id, &c);
    ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:151:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int s, w; scanf("%d %d", &s, &w);
              ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:205: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:208:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a[i], &b[i], &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:218:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:221: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: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27