oj.uz

Submission #260349

# Submission time Handle Problem Language Result Execution time Memory
260349 2020-08-10T06:23:41 Z dvdg6566 Colors (RMI18_colors) C++14
47 / 100
 3000 ms 7800 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4096 KB Output is correct
2 Correct 91 ms 4856 KB Output is correct
3 Correct 30 ms 4312 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 4096 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 4096 KB Output is correct
2 Correct 68 ms 4600 KB Output is correct
3 Correct 16 ms 4224 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 4096 KB Output is correct
2 Correct 68 ms 4600 KB Output is correct
3 Correct 16 ms 4224 KB Output is correct
4 Correct 379 ms 7240 KB Output is correct
5 Execution timed out 3062 ms 7800 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4096 KB Output is correct
2 Correct 91 ms 4856 KB Output is correct
3 Correct 30 ms 4312 KB Output is correct
4 Correct 183 ms 4096 KB Output is correct
5 Correct 68 ms 4600 KB Output is correct
6 Correct 16 ms 4224 KB Output is correct
7 Correct 197 ms 5752 KB Output is correct
8 Correct 77 ms 4656 KB Output is correct
9 Correct 30 ms 4224 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 4216 KB Output is correct
2 Execution timed out 3061 ms 6392 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 4096 KB Output is correct
2 Correct 45 ms 4480 KB Output is correct
3 Correct 48 ms 4352 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4096 KB Output is correct
2 Correct 91 ms 4856 KB Output is correct
3 Correct 30 ms 4312 KB Output is correct
4 Correct 223 ms 4096 KB Output is correct
5 Correct 183 ms 4096 KB Output is correct
6 Correct 68 ms 4600 KB Output is correct
7 Correct 16 ms 4224 KB Output is correct
8 Correct 379 ms 7240 KB Output is correct
9 Execution timed out 3062 ms 7800 KB Time limit exceeded
10 Halted 0 ms 0 KB -