Submission #1272651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272651		algoproclub	Colors (RMI18_colors)	C++20	0 / 100	325 ms	589824 KiB

colors

// UUID: ff987566-4ef5-4613-ba9a-b299058f9632
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int c=100000,k=18;
int fel[c][k];
array<int, 2> ert[c][k];
int be[c],ki[c],ido;
vector<int> adj[c];
array<int, 2> combine(array<int, 2> a, array<int, 2> b)
{
	return {min(a[0],b[0]),max(a[1],b[1])};
}
void dfs(int cs, int p)
{
	fel[cs][0]=p;
	be[cs]=++ido;
	for(int &x:adj[cs])
		if(x!=p) dfs(x,cs);
	ki[cs]=++ido;
}
bool ose(int a, int b)
{
	return(a==0 || be[a]<=be[b] && ki[b]<=ki[a]);
}
int lca(int a, int b)
{
	if(ose(a,b)) return a;
	if(ose(b,a)) return b;
	for(int i=k-1; i>=0; i--)
		if(!ose(fel[a][i],b)) a=fel[a][i];
	return fel[a][0];
}
array<int, 2> calc(int x, int lc)
{
	if(x==lc) return ert[x][0];
	array<int, 2> ans{n+10,0};
	for(int i=k-1; i>=0; i--)
		if(!ose(fel[x][i],lc))
		{
			ans=combine(ans,ert[x][i]);
			x=fel[x][i];
		}
	ans=combine(ans,ert[x][0]);
	return ans;
}
void solve()
{
	cin>>n>>m;
	ido=0;
	for(int i=0; i<=n; i++)
	{
		be[i]=ki[i]=0;
		adj[i].clear();
		for(int j=0; j<k; j++)
			fel[i][j]=0,ert[i][j]={n+10,0};
	}
	vector<int> hely(n+1);
	for(int i=1; i<=n; i++)
	{
		int x; cin>>x;
		hely[x]=i;
		ert[i][0][0]=x;
	}
	vector<vector<int>> pos(n+1);
	for(int i=1; i<=n; i++)
	{
		int x; cin>>x;
		ert[i][0][1]=x;
		pos[x].push_back(i);
	}
	while(m--)
	{
		int x,y; cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dfs(1,0);
	for(int j=1; j<k; j++)
		for(int i=1; i<=n; i++)
		{
			fel[i][j]=fel[fel[i][j-1]][j-1];
			ert[i][j]=combine(ert[i][j-1],ert[fel[i][j-1]][j-1]);
		}
	for(int i=1; i<=n; i++)
	{
		for(int &x:pos[i])
		{
			int lc=lca(x,hely[i]);
			array<int, 2> m=combine(calc(x,lc),calc(hely[i],lc));
			if(m[0]<i || m[1]>i)
			{
				cout<<"0\n";
				return;
			}
		}
	}
	cout<<"1\n";
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tc=1; cin>>tc;
	while(tc--) solve();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22