oj.uz

Submission #640884

# Submission time Handle Problem Language Result Execution time Memory
640884 2022-09-15T13:30:22 Z Tenis0206 Colors (RMI18_colors) C++11
100 / 100
 850 ms 82612 KB 
#include <bits/stdc++.h>

using namespace std;

int n,m;

int a[200005],b[200005];
bool sel[200005],ok[200005];

vector<int> G[200005],l[1000005],tr[200005],pr[200005];

bool e[200005];

struct dsu
{
    int t[200005],rang[200005];
    stack<pair<int,int>> st;
    dsu()
    {
        for(int i=1;i<=200000;i++)
        {
            rang[i] = 1, t[i] = 0;
        }
    }
    int reprezentant(int x)
    {
        if(!t[x])
        {
            return x;
        }
        return reprezentant(t[x]);
    }
    void uneste(int x, int y)
    {
        x = reprezentant(x);
        y = reprezentant(y);
        st.push({x,y});
        if(x==y)
        {
            return;
        }
        if(rang[x] > rang[y])
        {
            rang[x] += rang[y];
            t[y] = x;
        }
        else
        {
            rang[y] += rang[x];
            t[x] = y;
        }
    }
    void remove_last()
    {
        int x = st.top().first;
        int y = st.top().second;
        st.pop();
        if(x==y)
        {
            return;
        }
        if(x==t[y])
        {
            rang[x] -= rang[y];
            t[y] = 0;
        }
        else
        {
            rang[y] -= rang[x];
            t[x] = 0;
        }
    }
};

dsu d;

void add_node(int nod)
{
    sel[nod] = true;
    for(auto it : G[nod])
    {
        if(!sel[it])
        {
            continue;
        }
        d.uneste(nod,it);
    }
}

void remove_node(int nod)
{
    sel[nod] = false;
    for(int i=G[nod].size()-1;i>=0;i--)
    {
        int it = G[nod][i];
        if(!sel[it])
        {
            continue;
        }
        d.remove_last();
    }
}

void solve(int cul)
{
    for(auto it : tr[cul])
    {
        e[d.reprezentant(it)] = true;
    }
    for(auto it : pr[cul])
    {
        ok[it] = e[d.reprezentant(it)];
    }
    for(auto it : tr[cul])
    {
        e[d.reprezentant(it)] = false;
    }
}

void update(int ua, int ub, int val, int nod, int a, int b)
{
    if(ua<=a && ub>=b)
    {
        l[nod].push_back(val);
        return;
    }
    int mij = (a + b) >> 1;
    if(ua<=mij)
    {
        update(ua,ub,val,nod*2,a,mij);
    }
    if(ub>mij)
    {
        update(ua,ub,val,nod*2+1,mij+1,b);
    }
}

void solve_queries(int nod, int a, int b)
{
    for(auto it : l[nod])
    {
        add_node(it);
    }
    if(a==b)
    {
        solve(a);
        for(int i=l[nod].size()-1;i>=0;i--)
        {
            int it = l[nod][i];
            remove_node(it);
        }
        return;
    }
    int mij = (a + b) >> 1;
    solve_queries(nod*2,a,mij);
    solve_queries(nod*2+1,mij+1,b);
    for(int i=l[nod].size()-1;i>=0;i--)
    {
        int it = l[nod][i];
        remove_node(it);
    }
}

void solve_test()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tr[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        pr[b[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        update(b[i],a[i],i,1,1,n);
    }
    solve_queries(1,1,n);
    bool rez = true;
    for(int i=1;i<=n;i++)
    {
        if(!ok[i])
        {
            rez = false;
        }
        ok[i] = false;
        G[i].clear();
        tr[i].clear();
        pr[i].clear();
    }
    for(int i=1;i<=4*n;i++)
    {
        l[i].clear();
    }
    cout<<rez<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
   // freopen("nr.in","r",stdin);
   // freopen("nr.out","w",stdout);
    int t;
    cin>>t;
    for(int test=1;test<=t;test++)
    {
        solve_test();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 40900 KB Output is correct
2 Correct 40 ms 40052 KB Output is correct
3 Correct 22 ms 39748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 41152 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 40884 KB Output is correct
2 Correct 43 ms 39952 KB Output is correct
3 Correct 25 ms 39700 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 40884 KB Output is correct
2 Correct 43 ms 39952 KB Output is correct
3 Correct 25 ms 39700 KB Output is correct
4 Correct 162 ms 42552 KB Output is correct
5 Correct 490 ms 58588 KB Output is correct
6 Correct 850 ms 77216 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 40900 KB Output is correct
2 Correct 40 ms 40052 KB Output is correct
3 Correct 22 ms 39748 KB Output is correct
4 Correct 85 ms 40884 KB Output is correct
5 Correct 43 ms 39952 KB Output is correct
6 Correct 25 ms 39700 KB Output is correct
7 Correct 87 ms 41000 KB Output is correct
8 Correct 46 ms 40156 KB Output is correct
9 Correct 22 ms 39732 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 42552 KB Output is correct
2 Correct 503 ms 58464 KB Output is correct
3 Correct 514 ms 75728 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 40268 KB Output is correct
2 Correct 27 ms 39880 KB Output is correct
3 Correct 23 ms 39612 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 40900 KB Output is correct
2 Correct 40 ms 40052 KB Output is correct
3 Correct 22 ms 39748 KB Output is correct
4 Correct 68 ms 41152 KB Output is correct
5 Correct 85 ms 40884 KB Output is correct
6 Correct 43 ms 39952 KB Output is correct
7 Correct 25 ms 39700 KB Output is correct
8 Correct 162 ms 42552 KB Output is correct
9 Correct 490 ms 58588 KB Output is correct
10 Correct 850 ms 77216 KB Output is correct
11 Correct 87 ms 41000 KB Output is correct
12 Correct 46 ms 40156 KB Output is correct
13 Correct 22 ms 39732 KB Output is correct
14 Correct 164 ms 42552 KB Output is correct
15 Correct 503 ms 58464 KB Output is correct
16 Correct 514 ms 75728 KB Output is correct
17 Correct 45 ms 40268 KB Output is correct
18 Correct 27 ms 39880 KB Output is correct
19 Correct 23 ms 39612 KB Output is correct
20 Correct 93 ms 41936 KB Output is correct
21 Correct 460 ms 59208 KB Output is correct
22 Correct 774 ms 82612 KB Output is correct