oj.uz

Submission #224743

# Submission time Handle Problem Language Result Execution time Memory
224743 2020-04-18T17:37:55 Z nicolaalexandra Colors (RMI18_colors) C++14
22 / 100
 314 ms 5368 KB 
#include <bits/stdc++.h>
#define DIM 150010
#define INF 2000000000
using namespace std;
vector <int> L[DIM];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM];
int t,n,m,i,j,x,y;
int main (){

   // ifstream cin ("colors2.in");
   // ofstream cout ("colors2.out");

    cin>>t;
    for (int q=1;q<=t;q++){
        if (q == 36)
            q = 36;
        cin>>n>>m;

        for (i=1;i<=n;i++){
            L[i].clear();
            f[i] = 0;
        }

        for (i=1;i<=n;i++){
            cin>>a[i];
            f[a[i]]++;
        }

        int ok = 1;
        for (i=1;i<=n;i++){
            cin>>b[i];
            if (b[i] > a[i] || !f[b[i]])
                ok = 0;
            c[a[i]] = b[i];
        }
        for (i=1;i<=m;i++){
            cin>>x>>y;
            L[x].push_back(y);
            L[y].push_back(x);
        }

        if (!ok){
            cout<<0<<"\n";
            continue;
        }

        if (n == 1 && !m){
            if (a[1] == b[1])
                cout<<"1\n";
            else cout<<"0\n";
            continue;
        }

        if (n == 2 && m == 1){
            if ( (a[1] == b[1] && a[2] == b[2]) || (min (a[1],a[2]) == b[1] && min (a[1],a[2]) == b[2]) )
                cout<<"1\n";
            else cout<<"0\n";
            continue;
        }

        /// graf stea
        int nod = 0, cnt = 0;
        for (i=1;i<=n;i++){
            if (L[i].size() == 1)
                cnt++;
            else nod = i;
        }
        if (cnt == n-1){

            int maxi = 0, mini = n+1;
            for (i=1;i<=n;i++){
                if (b[i] == a[i])
                    continue;

                maxi = max (maxi,b[i]);
                if (i != nod)
                    mini = min (mini,b[i]);
            }
            if (maxi && (maxi > a[nod] || mini < b[nod])){
                cout<<"0\n";
                continue;
            }
            /// acum sa vad daca exista b[nod]
            int ok = 0;
            if (!maxi)
                ok = 1;
            for (i=1;i<=n;i++)
                if (i != nod && b[i] == b[nod]){
                    ok = 1;
                    break;
                }
            cout<<ok<<"\n";

            continue;
        }

        /// graf complet
        if (m == 1LL*n*(n-1)/2){

            cout<<1<<"\n";
            continue;
        }

    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5368 KB Output is correct
2 Correct 57 ms 4472 KB Output is correct
3 Correct 12 ms 3840 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 5368 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5368 KB Output is correct
2 Correct 57 ms 4472 KB Output is correct
3 Correct 12 ms 3840 KB Output is correct
4 Incorrect 152 ms 5240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5368 KB Output is correct
2 Correct 57 ms 4472 KB Output is correct
3 Correct 12 ms 3840 KB Output is correct
4 Correct 167 ms 5368 KB Output is correct
5 Incorrect 152 ms 5240 KB Output isn't correct
6 Halted 0 ms 0 KB -