Submission #1146341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146341		Zero_OP	Colors (RMI18_colors)	C++20	7 / 100	68 ms	5188 KiB

colors

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;

using pi = pair<int, int>;
using vpi = vector<pi>;
using vb = vector<bool>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 2e5 + 5;

int N, M, a[MAX], b[MAX];
vi adj[MAX];

void testcase(){
    cin >> N >> M;
    rep(i, 0, N) cin >> a[i];
    rep(i, 0, N) cin >> b[i];

    rep(i, 0, M){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    rep(i, 0, N){
        if(a[i] < b[i]){
            cout << 0 << '\n';
            return;
        }
    }

    vi idx(N);
    iota(all(idx), 0);
    sort(all(idx), [&](int i, int j){ return b[i] > b[j]; });

    for(auto u : idx){
        if(a[u] == b[u]) continue;
        assert(a[u] > b[u]);


        vb vis(N);
        queue<int> q; q.push(u);
        vis[u] = true;

        bool found = false;
        while(!q.empty()){
            int x = q.front(); q.pop();
            if(a[x] == b[u]){
                found = true;
                break;
            }

            for(auto y : adj[x]){
                if(!vis[y] && (b[y] <= b[u])){
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }

        if(found){
            a[u] = b[u];
        } else{
            cout << 0 << '\n';
            return;
        }
    }

    rep(i, 0, N){
        if(a[i] != b[i]){
            cout << 0 << '\n';
            return;
        }
    }
    cout << 1 << '\n';
}

void reset_data(){
    rep(i, 0, N) adj[i].clear();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int t;
    cin >> t;
    while(t--) testcase(), reset_data();

    return 0;
}

/*

Subtask 1 :

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

3 3
1 2 3
1 1 2
1 2
2 3
3 1

*/

• Subtask 1: 0 / 15
• Subtask 2: 7 / 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