Submission #1254389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254389		shjeong	Colors (RMI18_colors)	C++20	37 / 100	3093 ms	589824 KiB

colors

#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){
    vis[x]=1;
    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();
}

• 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: 0 / 10
• Subtask 8: 0 / 22