Submission #1254394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254394		shjeong	Colors (RMI18_colors)	C++20	100 / 100	587 ms	73600 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;
vector<ll> adj[151515];
vector<ll> A, B;
ll n;
struct UF_rollback{
    vector<ll> p, mn;
    stack<array<ll,5>> st;  //[병합한 두 정점, 병합된 쪽의 원래 p, 각각의 원래 mn]
//    UF_rollback(ll siz): p(siz+1,-1), mn(siz+1){}
    ll find(ll x){ if(p[x]<0)return x; return find(p[x]); }
    bool merge(ll x, ll y){
        x=find(x),y=find(y);
        if(x==y)return 0;
        if(-p[x] < -p[y]){
            swap(x,y);
        }
        st.push({x,y,p[y],mn[x],mn[y]});
        mn[x] = min(mn[x], mn[y]);
//        cout<<x<<" WOW "<<mn[x]<<endl;
        p[x] += p[y]; p[y] = x;
        return 1;
    }
    void rollback(ll t){
        while(t--){
            auto [u,v,P,m1,m2] = st.top(); st.pop();
            p[u] -= P;
            p[v] = P;
            mn[u] = m1, mn[v] = m2;
        }
    }
} uf;
vector<ll> wow[151515];
bool ok[151515];
bool ANS;
struct ODC{
    vector<vector<ll>> tree;
    ODC(ll siz): tree(siz*4){}
    void insert(ll node, ll s, ll e, ll l, ll r, ll x){
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            tree[node].push_back(x);
            return;
        }
        ll mid = s+e>>1;
        insert(node<<1,s,mid,l,r,x); insert(node<<1|1,mid+1,e,l,r,x);
    }
    void solve(ll node, ll s, ll e){
        int res = 0;
        for(auto i : tree[node]){
            ok[i]=1;
            for(auto next : adj[i])if(ok[next]){
                res += uf.merge(i,next);
            }
        }
        if(s==e){
            for(auto i : wow[s]){
                if(uf.mn[uf.find(i)] != B[i]){
                    ANS=0;
                    break;
                }
            }
        }
        else{
            ll mid = s+e>>1;
            solve(node<<1,s,mid);
            solve(node<<1|1,mid+1,e);
        }
        uf.rollback(res);
        for(auto i : tree[node])ok[i]=0;
    }
};
void solve(){
    ll m; cin>>n>>m;
    vector<ll> deg(n+1);
    A.resize(n+1); B.resize(n+1);
    set<ll> stA;
    uf.p.assign(n+1,-1);
    uf.mn.assign(n+1,-1);
    for(int i = 1 ; i <= n ; i++)adj[i].clear(), wow[i].clear();
    for(int i = 1 ; i <= n ; i++)cin>>A[i], stA.insert(A[i]), uf.mn[i] = 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; }
    ODC odc(n+1);
    for(int i = 1 ; i <= n ; i++)wow[B[i]].push_back(i);
    ANS = 1;
    for(int i = 1 ; i <= n ; i++)odc.insert(1,1,n,B[i],A[i],i);
    odc.solve(1,1,n);
    cout<<ANS<<"\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: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22