506D - Mr Kitayuta's Colorful Graph - CodeForces Solution

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma")
#pragma GCC target("popcnt")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef unsigned short us;
const int N=100005,B=128;
char inputbuf[1 << 23], *p1 = inputbuf, *p2 = inputbuf;
#define getchar() (p1 == p2 && (p2 = (p1 = inputbuf) + fread(inputbuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
	int res = 0; char ch = getchar(); bool f = true;
	for(; ch < '0' || ch > '9'; ch = getchar())
		if(ch == '-') f = false;
	for(; ch >= '0' && ch <= '9'; ch = getchar())
		res = res * 10 + (ch ^ 48);
	return f ? res : -res;
}
#define putchar_unlocked _putchar_nolock
void out_u32(unsigned int x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
#define rep(i,l,r) for (int i=l,i##end=r;i<i##end;++i)
namespace Hash1{
	const int S=19,S1=64-S;
	const ull M=1996090921996090921ull;
	#define H(x) (x*M>>S1)
	struct node{
		ull x; int y;
	}h[(1<<S)+105];
	inline void insert(ull x,int y=0){
		node *p=h+H(x);
		for (;p->x;++p)
			if (p->x==x){p->y=y; return;}
		p->x=x; p->y=y;
	}
	inline int* find(ull x){
		for (node *p=h+H(x);p->x;++p)
			if (p->x==x)return &p->y;
		return 0;
	}
	#undef H
} using namespace Hash1;

namespace mat{
	const int N=480,W=64,NB=8,w=8,h=8;
	ull a[N*NB],b[N*NB]; us c[N*N];
	void kernel(int x,int y,int l,int r){
		us t[w][h]{0};
		for (int k=l;k<r;++k)
			for (int i=0;i<w;++i)
				for (int j=0;j<h;++j)
					t[i][j]+=__builtin_popcountll(a[(x+i)*NB+k]&b[(y+j)*NB+k]);
		for (int i=0;i<w;++i)
			for (int j=0;j<h;++j)c[(x+i)*N+y+j]+=t[i][j];
	}
	void mat_mul_01_word(int n=N){
		const int s3=256,s2=8,s1=8;
		for (int i3=0;i3<n;i3+=s3)
			for (int i2=0;i2<n;i2+=s2)
				for (int i1=0;i1<NB;i1+=s1)
					for (int x=i2;x<min(i2+s2,n);x+=w)
						for (int y=i3;y<min(i3+s3,n);y+=h)
							kernel(x,y,i1,min(i1+s1,NB));
	}
}
using mat::W;

int v[N],X[N],Y[N],q[N],d[N],I[N],n,m,q0,L,L1,b1,d1,I1;
vector<pair<int,int>> edges[N];
vector<int> e[N],b_id[N];
bitset<B> b[N];
void dfs(int x){
	v[x]=1; d[d1++]=x;
	for (auto y:e[x])
		if (!v[y])dfs(y);
}
int main()
{
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int x,y,c;
	n=read(); m=read();
	rep(i,0,m){
		x=read(); y=read(); c=read();
		edges[c].emplace_back(x,y);
	}
	q0=read();
	++n; L=105; L1=90; ull n2=(ull)n*n;
	rep(i,0,q0){
		x=read(); y=read();
		if (x>y)swap(x,y);
		X[i]=x; Y[i]=y;
		insert((ull)x*n+y);
	}
	rep(c,1,m+1){
		int q1=0;
		for (auto &[x,y]:edges[c]){
			q[q1++]=x; q[q1++]=y;
			e[x].push_back(y); e[y].push_back(x);
		}
		rep(i,0,q1){
			int x=q[i];
			if (!v[x]){
				d1=0; dfs(x);
				if (d1<L){
					//sort(d,d+d1);
					rep(j,0,d1)
						rep(k,j+1,d1){
							int x1=d[j],y1=d[k];
							int *p=find(x1<y1?(ull)x1*n+y1:(ull)y1*n+x1);
							if (p)++*p;
						}
				}
				else {
					rep(j,0,d1){
						int x=d[j]; b[x].set(b1,1);
						b_id[x].push_back(b1);
					}
					++b1;
				}
			}
		}
		rep(i,0,q1)v[q[i]]=0,e[q[i]].clear();
	}
	assert(b1<mat::N);
	rep(i,0,n-1)
		if (b_id[i].size()>L1){
			for (auto t:b_id[i]){
				mat::a[I1*mat::NB+t/W]|=1ull<<t%W;
				mat::b[I1*mat::NB+t/W]|=1ull<<t%W;
			}
			I[i]=I1++;
		}
	mat::mat_mul_01_word();
	rep(i,0,q0){
		int x1=X[i],y1=Y[i],ans=*find((ull)x1*n+y1);
		//+(b[x1]&b[y1]).count()
		if (b_id[x1].size()>b_id[y1].size())swap(x1,y1);
		if (b_id[x1].size()<=L1)for (auto t:b_id[x1])ans+=b[y1][t];
		else ans+=int(mat::c[I[x1]*mat::N+I[y1]]+0.5);
		out_u32(ans); putchar_unlocked('\n');
	}
	//system("pause");for (;;);
	return 0;
}