제출 #1231342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231342		denislav	Colors (RMI18_colors)	C++20	100 / 100	526 ms	112032 KiB

colors

# include <iostream>
# include <vector>
using namespace std;

const int MAX=4e5+11;

bool f=1;
int n,m;
int c[MAX];
int d[MAX];
vector<int> col[MAX];
vector<int> new_col[MAX];

vector<pair<int,int>> tree[MAX*4];

void add(int le, int ri, pair<int,int> pa, int v=1, int l=1, int r=n)
{
    if(ri<l or r<le) return ;
    if(le<=l and r<=ri)
    {
        tree[v].push_back(pa);
        return ;
    }

    int mid=(l+r)/2;
    add(le,ri,pa,v*2,l,mid);
    add(le,ri,pa,v*2+1,mid+1,r);
}

struct Change
{
    int tm;
    int* ptr;
    int last_val;
};

struct dsu
{
    int par[MAX];
    int sz[MAX];
    int timer;
    vector<Change> ve;

    void init()
    {
        timer=0;
        ve.clear();
        for(int i=1;i<=n;i++)
        {
            sz[i]=1;
            par[i]=i;
        }
    }

    int root(int x)
    {
        if(par[x]==x) return x;
        return root(par[x]);
    }

    void unite(int u, int v)
    {
        u=root(u);v=root(v);

        timer++;
        if(u==v) return ;
        if(sz[u]<sz[v]) swap(u,v);
        ve.push_back({timer,par+v,par[v]});
        ve.push_back({timer,sz+u,sz[u]});

        par[v]=u;
        sz[u]+=sz[v];
    }

    void undo()
    {
        timer--;
        while(ve.size()>0 and ve.back().tm>timer)
        {
            (*ve.back().ptr)=ve.back().last_val;
            ve.pop_back();
        }
    }
}dsu;

void rec(int v=1, int l=1, int r=n)
{
    for(pair<int,int> pa: tree[v]) dsu.unite(pa.first,pa.second);

    if(l!=r)
    {
        int mid=(l+r)/2;
        rec(v*2,l,mid);
        rec(v*2+1,mid+1,r);
    }
    else
    {
        if(new_col[l].size()>0 and col[l].size()==0) f=0;
        else
        for(int i=0;i<(int)new_col[l].size();i++)
        {
            if(dsu.root(new_col[l][i])!=dsu.root(col[l][0])) f=0;
        }
    }

    for(pair<int,int> pa: tree[v]) dsu.undo();
}

void reset()
{
    f=1;
    for(int i=1;i<=n*4;i++) tree[i].clear();
    for(int i=1;i<=n;i++)
    {
        col[i].clear();
        new_col[i].clear();
    }
}

void solve()
{
    cin>>n>>m;
    reset();
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        col[c[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
        new_col[d[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(max(d[u],d[v])<=min(c[u],c[v])) add(max(d[u],d[v]),min(c[u],c[v]),{u,v});
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(int)col[i].size()-1;j++) add(i,i,{col[i][j],col[i][j+1]});
    }

    for(int i=1;i<=n;i++)
    {
        if(c[i]<d[i]) f=0;
    }
    if(!f)
    {
        cout<<0<<"\n";
        return ;
    }

    dsu.init();
    rec();

    cout<<f<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}

• 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