oj.uz

Submission #700477

# Submission time Handle Problem Language Result Execution time Memory
700477 2023-02-19T06:48:30 Z Nursik Colors (RMI18_colors) C++14
15 / 100
 158 ms 70844 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double

const ll maxn = 1e6 + 1, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blck = 400, p2 = 31;
const ld eps = 1e-9;

int t;
int n, m;
int a[maxn], b[maxn];
int used[maxn];
set<int> setik[maxn];
vector<int> g[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m;
        for (int i = 1; i <= n; ++i){
            cin >> a[i];
            used[a[i]] = 1;
            setik[a[i]].insert(i);
        }
        for (int i = 1; i <= n; ++i){
            cin >> b[i];
        }
        for (int i = 1; i < n; ++i){
            int u, v;
            cin >> u >> v;
            g[u].pb(v);
            g[v].pb(u);
        }
        int star = 0, complt = (n * (n - 1) / 2 == m);
        if (complt){
            vector<pair<int, int>> vec;
            for (int i = 1; i <= n; ++i){
                vec.pb(mp(b[i], i));
            }
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            int bad = 0;
            for (int i = 0; i < n; ++i){
                int x = vec[i].f, y = vec[i].s;
                int ok = 0;
                for (int j = 1; j <= n; ++j){
                    if (a[j] == x){
                        ok = 1;
                        a[y] = min(a[y], a[j]);
                        break;
                    }
                }
                bad |= !ok;
            }
            for (int i = 1; i <= n; ++i){
                if (a[i] != b[i]){
                    bad = 1;
                }
            }
            if (bad){
                cout << 0 << '\n';
            }
            else{
                cout << 1 << '\n';
            }
            for (int i = 1; i <= n; ++i){
                setik[i].clear();
                used[i] = 0;
                g[i].clear();
            }
            continue;
        }
        for (int i = 1; i <= n; ++i){
            if ((int)g[i].size() == n - 1){
                star = i;
            }
        }
        if (star){
            int bad = 0;
            vector<pair<int, int>> vec;
            for (int i = 1; i <= n; ++i){
                vec.pb(mp(b[i], i));
            }
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            for (int i = 0; i < n; ++i){
                pair<int, int> cur = vec[i];
                int x = cur.f;
                int y = cur.s;
                if (a[y] == b[y]){
                    setik[a[y]].insert(y);
                    continue;
                }
                if ((int)setik[x].size() == 0){
                    bad = 1;
                    break;
                }
                int z = *setik[x].begin();
                setik[a[star]].erase(star);
                a[star] = min(a[star], a[z]);
                setik[a[star]].insert(star);
                setik[a[y]].erase(y);
                a[y] = min(a[y], a[star]);
                setik[a[y]].insert(y);
            }
            for (int i = 1; i <= n; ++i){
                if (a[i] != b[i]){
                    bad = 1;
                }
            }
            if (bad){
                cout << 0 << '\n';
            }
            else{
                cout << 1 << '\n';
            }
        }
        for (int i = 1; i <= n; ++i){
            used[i] = 0;
            g[i].clear();
            setik[i].clear();
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 70800 KB Output is correct
2 Correct 67 ms 70844 KB Output is correct
3 Correct 43 ms 70804 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 70800 KB Output is correct
2 Correct 67 ms 70844 KB Output is correct
3 Correct 43 ms 70804 KB Output is correct
4 Incorrect 85 ms 70732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 70800 KB Output is correct
2 Correct 67 ms 70844 KB Output is correct
3 Correct 43 ms 70804 KB Output is correct
4 Incorrect 45 ms 70760 KB Output isn't correct
5 Halted 0 ms 0 KB -