Submission #1272624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272624		algoproclub	Colors (RMI18_colors)	C++20	47 / 100	3094 ms	4432 KiB

colors

// UUID: a3867fbe-5425-4762-a1d3-96389e0df7e3
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int c=150005;
int fonok[c],mer[c];
int holvan(int x)
{
	return (fonok[x]==x?x:fonok[x]=holvan(fonok[x]));
}
void unio(int a, int b)
{
	a=holvan(a),b=holvan(b);
	if(a==b) return;
	if(mer[a]>mer[b]) swap(a,b);
	mer[b]+=mer[a];
	fonok[a]=b;
}
void solve()
{
	cin>>n>>m;
	vector<int> a(n+1),b(n+1);
	for(int i=1; i<=n; i++)
		cin>>a[i];
	for(int i=1; i<=n; i++)
		cin>>b[i];
	vector<array<int, 2>> elek(m);
	for(auto &[a,b]:elek) cin>>a>>b;
	vector<vector<int>> pos1(n+1),pos2(n+1);
	for(int i=1; i<=n; i++)
	{
		pos1[a[i]].push_back(i);
	}
	for(int i=1; i<=n; i++)
	{
		pos2[b[i]].push_back(i);
	}
	for(int i=n; i>0; i--)
	{
		if(pos1[i].empty() && !pos2[i].empty())
		{
			cout<<"0\n";
			return;
		}
		if(pos1[i].empty() && pos2[i].empty()) continue;
		for(int i=1; i<=n; i++)
			fonok[i]=i,mer[i]=1;
		for(auto &[x,y]:elek)
		{
			if(a[x]>=i && a[y]>=i && b[x]<=i && b[y]<=i) unio(x,y); 
		}
		vector<bool> van(n+1);
		for(int &x:pos1[i])
			van[holvan(x)]=1;
		for(int &x:pos2[i])
			if(!van[holvan(x)])
			{
				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: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 0 / 15
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 10 / 10
• Subtask 8: 0 / 22