Submission #225374

#TimeUsernameProblemLanguageResultExecution timeMemory
225374nicolaalexandraColors (RMI18_colors)C++14
45 / 100
696 ms46584 KiB
#include <bits/stdc++.h> #define DIM 150010 #define INF 2000000000 using namespace std; vector <int> L[DIM],poz[DIM*4]; int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM],v[DIM],viz[DIM]; int t,n,m,i,j,x,y,k,sol,mini,maxi; struct seg_tree{ int minia,maxib; } aint[4*DIM]; void dfs (int nod){ viz[nod] = 1; v[++k] = nod; for (auto vecin : L[nod]) if (!viz[vecin]) dfs (vecin); } void build (int nod, int st, int dr){ if (st == dr){ aint[nod].minia = a[v[st]]; aint[nod].maxib = b[v[st]]; return; } int mid = (st+dr)>>1; build (nod<<1,st,mid); build ((nod<<1)|1,mid+1,dr); aint[nod].minia = min (aint[nod<<1].minia,aint[(nod<<1)|1].minia); aint[nod].maxib = max (aint[nod<<1].maxib,aint[(nod<<1)|1].maxib); } void query (int nod, int st, int dr, int x, int y){ if (x <= st && dr <= y){ mini = min (mini,aint[nod].minia); maxi = max (maxi,aint[nod].maxib); return; } int mid = (st+dr)>>1; if (x <= mid) query(nod<<1,st,mid,x,y); if (y > mid) query ((nod<<1)|1,mid+1,dr,x,y); } int solve (int v[], int k){ for (i=1;i<=4*k;i++){ poz[i].clear(); aint[i] = {0,0}; } for (i=1;i<=k;i++) poz[a[v[i]]].push_back(i); build (1,1,k); int ok = 1; for (i=1;i<=k;i++){ if (a[v[i]] == b[v[i]]) continue; int lft = 0, rgh = 0; for (auto it : poz[b[v[i]]]){ if (it < i) lft = it; if (it > i){ rgh = it; break; } } int ok2 = 0; if (lft){ mini = INF, maxi = -INF; query (1,1,k,lft,i-1); if (mini >= b[v[i]] && maxi <= b[v[i]]) ok2 = 1; } if (rgh){ mini = INF, maxi = -INF; query (1,1,k,i+1,rgh); if (mini >= b[v[i]] && maxi <= b[v[i]]) ok2 = 1; } if (!ok2){ ok = 0; break; } } return ok; } int main (){ // ifstream cin ("colors2.in"); // ofstream cout ("colors2.out"); cin>>t; for (int q=1;q<=t;q++){ if (q == 36) q = 36; cin>>n>>m; for (i=1;i<=n;i++){ L[i].clear(); f[i] = 0; } for (i=1;i<=n;i++){ cin>>a[i]; f[a[i]]++; } int ok = 1; for (i=1;i<=n;i++){ cin>>b[i]; if (b[i] > a[i] || !f[b[i]]) ok = 0; } for (i=1;i<=m;i++){ cin>>x>>y; L[x].push_back(y); L[y].push_back(x); } if (!ok){ cout<<0<<"\n"; continue; } if (n == 1 && !m){ if (a[1] == b[1]) cout<<"1\n"; else cout<<"0\n"; continue; } if (n == 2 && m == 1){ if ( (a[1] == b[1] && a[2] == b[2]) || (min (a[1],a[2]) == b[1] && min (a[1],a[2]) == b[2]) ) cout<<"1\n"; else cout<<"0\n"; continue; } /// graf stea int nod = 0, cnt = 0; for (i=1;i<=n;i++){ if (L[i].size() == 1) cnt++; else nod = i; } if (cnt == n-1){ int maxi = 0, mini = n+1; for (i=1;i<=n;i++){ if (b[i] == a[i]) continue; maxi = max (maxi,b[i]); if (i != nod) mini = min (mini,b[i]); } if (maxi && (maxi > a[nod] || mini < b[nod])){ cout<<"0\n"; continue; } /// acum sa vad daca exista b[nod] int ok = 0; if (!maxi) ok = 1; for (i=1;i<=n;i++) if (i != nod && b[i] == b[nod]){ ok = 1; break; } cout<<ok<<"\n"; continue; } /// graf complet if (m == 1LL*n*(n-1)/2){ cout<<1<<"\n"; continue; } /// lant int start = 0; for (i=1;i<=n;i++) if (L[i].size() == 1){ start = i; break; } memset (viz,0,sizeof viz); k = 0; dfs (start); if (solve (v,k)) cout<<"1\n"; else cout<<"0\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...