Submission #374810

#	Time	Username	Problem	Language	Result	Execution time	Memory
374810		AriaH	Bridges (APIO19_bridges)	C++11	27 / 100	3051 ms	7152 KiB

bridges

/** I can do this all day **/

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int B = 800;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

struct edge
{
	int u, v, w, id;
} org[N], E[N];

bool cmp(edge a, edge b)
{
	return a.w > b.w;
}

int n, m, q, tp[N], fir[N], sec[N], change[N], par[N], sz[N], Ans[N];

vector < pii > hist;

bool cmp2(int i, int j)
{
	return sec[i] > sec[j];
}

int get(int x) { return (x == par[x]? x : get(par[x])); }

inline void unify(int v, int u)
{
	///printf("merging v = %d u = %d\n", v, u);
	v = get(v), u = get(u);
	if(v == u)
	{
		hist.push_back(Mp(0, 0));
		return;
	}
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
	hist.push_back(Mp(u, v));
}

inline void undo()
{
	if(hist.empty()) return;
	pii cu = hist.back();
	hist.pop_back();
	par[cu.F] = cu.F;
	sz[cu.S] -= sz[cu.F];
}

void solve(int l, int r)
{
	///printf("baze = %d %d\n", l, r);
	if(l > r) return;
	hist.clear();
	for(int i = 1; i <= n; i ++) par[i] = i, sz[i] = 1;
	memset(change, 0, sizeof change);
	vector < int > WTF;
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			if(change[fir[i]]) continue;
			change[fir[i]] = 1;
			WTF.push_back(i);
		}
	}
	for(int i = 1; i <= m; i ++) E[i] = org[i];
	sort(E + 1, E + m + 1, cmp);
	/*for(int i = 1; i <= m; i ++)
	{
		printf("%d %d %d %d\n", E[i].v, E[i].u, E[i].w, change[E[i].id]);
	}
	*/
	vector < int > Q;
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1) continue;
		Q.push_back(i);
	}
	sort(all(Q), cmp2);
	int last = 1;
	for(auto i : Q)
	{
		
		while(last <= m && sec[i] <= E[last].w)
		{
			if(change[E[last].id] == 0)
			{
				///printf("merged v = %d u = %d id = %d\n", E[last].v, E[last].u, E[last].id);
				unify(E[last].v, E[last].u);
			}
			last ++;
		}
		hist.clear();
		///printf("i = %d fir = %d sec = %d last = %d sz = %d\n", i, fir[i], sec[i], last, sz[get(fir[i])]);
		set < int > used;
		for(int j = i; j >= l; j --)
		{
			if(tp[j] == 1)
			{
				if(used.count(fir[j]) > 0) continue;
				used.insert(fir[j]);
				if(sec[j] < sec[i]) continue;
				unify(org[fir[j]].v, org[fir[j]].u);
			}
		}
		for(auto cu : WTF)
		{
			if(cu <= i) continue;
			if(org[fir[cu]].w < sec[i]) continue;
			unify(org[fir[cu]].v, org[fir[cu]].u);

		}
		Ans[i] = sz[get(fir[i])];
		///printf("Ans = %d\n", Ans[i]);
		int Sz = SZ(hist);
		for(int _ = 0; _ < Sz; _++)
		{
			undo();
			///printf("undo\n");
		}
	}
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			org[fir[i]].w = sec[i];
		}
	}

}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d%d", &org[i].v, &org[i].u, &org[i].w);
		org[i].id = i;
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i ++)
	{
		scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
		if(i % B == 0)
		{
			solve(i - B + 1, i);
		}
	}
	solve(q / B * B + 1, q);
	for(int i = 1; i <= q; i ++)
	{
		if(tp[i] == 2) printf("%d\n", Ans[i]);
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

bridges.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |   scanf("%d%d%d", &org[i].v, &org[i].u, &org[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  166 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |   scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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