Submission #260349

#	Time	Username	Problem	Language	Result	Execution time	Memory
260349		dvdg6566	Colors (RMI18_colors)	C++14	47 / 100	3062 ms	7800 KiB

colors

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 160000;
const ll BSIZ= 800;

int T,N,E,a,b;
int A[MAXN];
int B[MAXN];
vi V[MAXN];
int vis[MAXN];

void dfs(int x,int col){
	vis[x]=1;
	for(auto v:V[x])if(!vis[v]){
		if(B[v]>col||A[v]<col)continue;
		dfs(v,col);
	}
}

int main(){
 	cin>>T;
 	while(T--){
 		cin>>N>>E;
 		for(int i=1;i<=N;++i){
 			V[i].clear();
 			cin>>A[i];
 		}
 		for(int i=1;i<=N;++i)cin>>B[i];
 		for(int i=0;i<E;++i){cin>>a>>b;V[a].pb(b);V[b].pb(a);}
 		int ans=1;
 		for(int col=1;col<=N;++col)if(ans){
 			for(int j=1;j<=N;++j)vis[j]=0;
 			for(int j=1;j<=N;++j)if(!vis[j]&&A[j]==col)dfs(j,col);
 			for(int j=1;j<=N;++j)if(B[j]==col&&!vis[j]){
 				ans=0;
 				break;
 			}
 		}
 		cout<<ans<<'\n';
 	}
}

• 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