| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 873465 |
2023-11-15T06:36:21 Z |
vjudge1 |
Colors (RMI18_colors) |
C++17 |
|
107 ms |
21332 KB |
// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int P = 31;
const int K = 400;
const ll inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9+7;
const int maxn = 2e5 + 10;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
int timer;
int a[maxn];
int b[maxn];
int c[maxn];
int n, m, sz;
int us[maxn];
int tin[maxn];
int t[2][maxn*4];
vector<int>g[maxn];
map<int, int>dp[maxn];
int dfs(int v, int x){
us[v] = sz;
if(a[v] < x) return 0;
if(b[v] > x) return 0;
if(a[v] == x) return 1;
int ans = 0;
for(int to: g[v]){
if(us[to] < sz && dfs(to, x)) {
ans = 1;
break;
}
}
return ans;
}
void dfs1(int v, int pr){
tin[v] = ++timer;
c[tin[v]] = v;
for(int to: g[v]){
if(to != pr)
dfs1(to, v);
}
}
void build(int v=1, int tl=1, int tr=n){
if(tl == tr){
t[0][v] = a[c[tl]];
t[1][v] = b[c[tl]];
} else{
int tm = tl+tr>>1;
build(v<<1, tl, tm);
build(v<<1|1, tm+1, tr);
t[0][v] = min(t[0][v<<1], t[0][v<<1|1]);
t[1][v] = max(t[1][v<<1], t[1][v<<1|1]);
}
}
pii merge(pii a, pii b){
return {min(a.f, b.f), max(a.s, b.s)};
}
pii get(int l, int r, int v=1, int tl=1, int tr=n){
if(l > tr || r < tl) return {inf, 0};
if(l <= tl && tr <= r) return {t[0][v], t[1][v]};
int tm = tl+tr>>1;
return merge(get(l, r, v<<1, tl, tm), get(l, r, v<<1|1, tm+1, tr));
}
int ihtw1(){
sz++;
timer = 0;
for(int i=1; i<=n; i++){
if(sz(g[i]) == 1){
dfs1(i, 0);
break;
}
}
build();
map<int, int>mp;
for(int it=1; it<=n; it++){
int i = c[it];
mp[a[i]] = it;
if(mp[b[i]]){
pii x = get(mp[b[i]], it);
if(x.f >= b[i] && x.s <= b[i])
us[i] = sz;
}
} mp.clear();
for(int it=n; it>0; it--){
int i = c[it];
mp[a[i]] = it;
if(mp[b[i]]){
pii x = get(it, mp[b[i]]);
if(x.f >= b[i] && x.s <= b[i])
us[i] = sz;
}
} int ans = 1;
for(int i=1; i<=n; i++) ans &= (us[i]==sz);
return ans;
}
void ihtw(){
set<int>st;
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) {
cin >> b[i];
g[i].clear();
dp[i].clear();
st.insert(a[i]);
}
for(int i=0; i<m; i++){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
} bool ok = 1;
for(int i=1; i<=n; i++){
if(sz(g[i]) > 2) ok = 0;
}
if(m == n-1 && ok) {
cout << ihtw1() << "\n";
return;
}
// if(m == n-1 && sz(st) == n) ihtw2();
for(int i=1; i<=n; i++){
sz++;
if(!dfs(i, b[i])){
cout << "0\n";
return;
}
} cout << "1\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--) ihtw();
}
Compilation message
colors.cpp: In function 'void build(int, int, int)':
colors.cpp:63:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int tm = tl+tr>>1;
| ~~^~~
colors.cpp: In function 'pii get(int, int, int, int, int)':
colors.cpp:78:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int tm = tl+tr>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
21080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
21080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
21332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
21080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
21080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
