oj.uz

Submission #858267

# Submission time Handle Problem Language Result Execution time Memory
858267 2023-10-07T20:27:55 Z heeheeheehaaw Colors (RMI18_colors) C++17
0 / 100
 170 ms 17596 KB 
#include <bits/stdc++.h>
using namespace std;

int t, n, m;
vector<int> adj[150005], ci[150005], cf[150005];
int parent[150005], sz[150005], timec[150005];
int last[150005], c1[150005], c2[150005];
bool ex[150005], aux[150005];

int cauta(int u, int tm)
{
    if(u == parent[u] || timec[u] > tm)
        return u;
    return cauta(parent[u], tm);
}

void unite(int u, int v, int tm)
{
    u = cauta(u, tm);
    v = cauta(v, tm);
    if(u == v) return;
    if(sz[u] > sz[v]) swap(u, v);
    parent[u] = v;
    sz[v] += sz[u];
    timec[u] = tm;
}

signed main()
{
    cin>>t;
    while(t--)
    {
        bool ok = true;
        cin>>n>>m;
        
        for(int i = 1; i <= n; i++)
        {
            adj[i].clear();
            ci[i].clear();
            cf[i].clear();
            last[i] = 0;
            ex[i] = 0;
            aux[i] = 0;
            c1[i] = 0;
            c2[i] = 0;
            timec[i] = 0;
        }
        
        for(int i = 1; i <= n; i++) cin>>c1[i], ci[c1[i]].push_back(i);
        for(int i = 1; i <= n; i++) cin>>c2[i], cf[c2[i]].push_back(i);
        
        for(int i = 1; i <= n; i++)
        {
            ex[i] = 0;
            parent[i] = i;
            sz[i] = 1;
            timec[i] = 0;
            if(c2[i] > c1[i])
                ok = false;
        }
        
        if(!ok)
        {
            cout<<0<<'\n';
            continue;
        }
        
        for(int i = 1; i <= m; i++)
        {
            int a, b;
            cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        int timer = 0;
        for(int c = 1; c <= n; c++)
        {
            last[c] = timer;
            //cout<<c<<" "<<last[c]<<" ZZZ\n";
            for(auto i : cf[c])
            {
                ex[i] = true;
                for(auto j : adj[i])
                    if(ex[j])
                    {
                        unite(i, j, ++timer);
                    }
                        
            }
        }
        last[n + 1] = timer;
        
        bool ans = true;
        for(int c = n; c >= 1; c--)
        {
            timer = last[c + 1];
            //cout<<c<<" "<<timer<<" zzz "<<'\n';
            vector<int> idk;
            
            for(auto nod : ci[c])
            {
                int val = cauta(nod, timer);
                //cout<<"nod: "<<nod<<", timer: "<<timer<<", val: "<<val<<'\n';
                aux[val] = true;
                idk.push_back(val);
            }
            
            for(auto nod : cf[c])
            {
                int val = cauta(nod, timer);
                //cout<<"ZZZ nod: "<<nod<<" val: "<<val<<'\n';
                if(aux[val] == false)
                    ans = false;
            }
            
            for(auto nod : idk)
                aux[nod] = false;
            
        }
        
        cout<<ans;
    }
    
    return 0;
}

/**

2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2


*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 16048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 15192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 16048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 17596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 16048 KB Output isn't correct
2 Halted 0 ms 0 KB -