Submission #1254388

#TimeUsernameProblemLanguageResultExecution timeMemory
1254388shjeongColors (RMI18_colors)C++20
0 / 100
301 ms589824 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma optimize("unroll-loops") #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define COMP(x) x.erase(unique(all(x)), x.end()) #define MOD 1000000007 #define MOD2 998244353 #define sz(x) (ll)x.size() typedef __int128_t lll; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pll; typedef pair<ll, pll> PP; const ll Lnf = 2e18; array<ll,2> S[151515]; vector<ll> adj[151515]; struct segtree{ vector<array<ll,2>> tree; segtree(ll siz): tree(siz*4){} void init(ll node, ll s, ll e){ if(s==e)tree[node] = S[s]; else{ ll mid = s+e>>1; init(node<<1,s,mid); init(node<<1|1,mid+1,e); tree[node] = {max(tree[node<<1][0],tree[node<<1|1][0]), min(tree[node<<1|1][1],tree[node<<1][1])}; } } array<ll,2> query(ll node, ll s, ll e, ll l, ll r){ if(e<l or r<s)return {-Lnf,Lnf}; if(l<=s and e<=r)return tree[node]; ll mid = s+e>>1; auto [a,b] =query(node<<1,s,mid,l,r); auto [c,d] =query(node<<1|1,mid+1,e,l,r); return {max(a,c),min(b,d)}; } }; vector<ll> v; void dfs(ll x, ll prv=-1){ v.push_back(x); for(auto next : adj[x])if(prv!=next)dfs(next,x); } vector<bool> vis; bool dfs2(ll x, ll cur, ll prv, vector<ll>&A, vector<ll> &B){ if(B[x]>cur or A[x]<cur)return 0; if(A[x] == cur)return 1; for(auto next : adj[x])if(!vis[next]){ if(dfs2(next,cur,x,A,B))return 1; } return 0; } void solve(){ ll n, m; cin>>n>>m; vector<ll> deg(n+1); vector<ll> A(n+1), B(n+1); set<ll> stA; v.clear(); for(int i = 1 ; i <= n ; i++)adj[i].clear(); for(int i = 1 ; i <= n ; i++)cin>>A[i], stA.insert(A[i]); for(int i = 1 ; i <= n ; i++)cin>>B[i]; for(int i = 0 ; i < m ; i++){ ll a,b; cin>>a>>b; deg[a]++; deg[b]++; adj[a].push_back(b); adj[b].push_back(a); } for(int i = 1 ; i <= n ; i++)if(A[i]<B[i]){ cout<<"0\n"; return; } for(int i = 1 ; i <= n ; i++)if(!stA.contains(B[i])){ cout<<"0\n"; return; } segtree seg(n+1); vector<ll> num(n+1); for(int i = 1 ; i <= n ; i++){ if(!sz(v) and deg[i] == 1){ v.push_back(0); dfs(i); for(int j = 1 ; j <= n ; j++)num[v[j]] = j; break; } } for(int i = 1 ; i <= n ; i++){ vis.assign(n+1,0); if(!dfs2(i,B[i],-1,A,B)){ cout<<"0\n"; return; } } cout<<"1\n"; return; for(int i = 1 ; i <= n ; i++){ // cout<<num[i]<<" \n"[i==n]; S[num[i]] = {B[i],A[i]}; } seg.init(1,1,n); for(int i = 1 ; i <= n ; i++)if(A[v[i]]!=B[v[i]]){ // cout<<i<<" "<<v[i]<<endl; //1. 왼쪽으로 몇칸 if(i>1){ ll l = 0, r = i; ll lx = B[v[i]], ly = A[v[i]]; while(l+1 < r){ ll mid = l+r>>1; auto [x,y] = seg.query(1,1,n,i-mid,i); // cout<<mid<<" "<<x<<" "<<y<<endl; if(x <= B[v[i]] and B[v[i]] <= y)l = mid, lx = x, ly = y; else r = mid; } if(ly == B[v[i]])continue; } if(i<n){ ll l = 0, r = n-i+1; ll lx = B[v[i]], ly = A[v[i]]; while(l+1 < r){ ll mid = l+r>>1; auto [x,y] = seg.query(1,1,n,i,i+mid); if(x <= B[v[i]] and B[v[i]] <= y)l = mid, lx = x, ly = y; else r = mid; } if(ly == B[v[i]])continue; } cout<<"0\n"; return; } cout<<"1\n"; } int main(){ fast; ll t; cin>>t; while(t--)solve(); }
#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...