Submission #374821

#	Time	Username	Problem	Language	Result	Execution time	Memory
374821		AriaH	Bridges (APIO19_bridges)	C++17	59 / 100	3074 ms	4596 KiB

bridges

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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast, O2, unroll-loops")
#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 + 2;
const int N2 = 5e4 + 2;
const int B = 650;

int U[N], V[N], W[N], E[N];

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

pii hist[N];

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

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

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

inline void Unify(int v, int u)
{
    v = Get(v), u = Get(u);
    if(v == u) return;
    if(sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

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

inline void unify(int v, int u)
{
	v = get(v), u = get(u);
	if(v == u)
	{
		hist[ptr ++] = Mp(0, 0);
		return;
	}
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
	hist[ptr ++] = Mp(u, v);
}

inline void undo()
{
	if(ptr == 0) return;
	pii cu = hist[ptr - 1];
	ptr --;
	par[cu.F] = cu.F;
	sz[cu.S] -= sz[cu.F];
}

void solve(int l, int r)
{
	if(l > r) return;
	ptr = 0;
	for(int i = 1; i <= n; i ++) par[i] = i, sz[i] = 1;
	memset(change, 0, sizeof change);
	memset(mark, 0, sizeof mark);
	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] = i;
	sort(E + 1, E + m + 1, cmp);
	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] <= W[E[last]])
		{
			if(change[E[last]] == 0)
			{
				Unify(V[E[last]], U[E[last]]);
			}
			last ++;
		}
		for(int j = i; j >= l; j --)
		{
			if(tp[j] == 1)
			{
				if(mark[fir[j]]) continue;
				mark[fir[j]] = 1;
				if(sec[j] < sec[i]) continue;
				unify(V[fir[j]], U[fir[j]]);
			}
		}
		for(int j = i; j >= l; j --) mark[fir[j]] = 0;
		for(auto cu : WTF)
		{
			if(cu <= i) continue;
			if(W[fir[cu]] < sec[i]) continue;
			unify(V[fir[cu]], U[fir[cu]]);

		}
		Ans[i] = sz[get(fir[i])];
		while(ptr)
		{
		    undo();
		}		    
	}
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			W[fir[i]] = sec[i];
		}
	}

}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d%d", &V[i], &U[i], &W[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:4:47: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("Ofast, O2, unroll-loops")
      |                                               ^
bridges.cpp:4:47: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
      |                                                                 ^
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
bridges.cpp:5:65: warning: bad option '-f O2' t

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