제출 #374825

#제출 시각아이디문제언어결과실행 시간메모리
374825AriaHBridges (APIO19_bridges)C++11
59 / 100
3083 ms4652 KiB
/** I can do this all day **/

#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 + 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;
	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)
	{
		ptr = 0;
		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 **/

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |   scanf("%d%d%d", &V[i], &U[i], &W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...