Submission #858267

#	Time	Username	Problem	Language	Result	Execution time	Memory
858267		heeheeheehaaw	Colors (RMI18_colors)	C++17	0 / 100	170 ms	17596 KiB

colors

#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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22