Submission #1146317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146317		Zero_OP	Colors (RMI18_colors)	C++20	22 / 100	41 ms	5188 KiB

colors

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define all(v) begin(v), end(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>;

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];

namespace subtask1{ //star graph
    bool check(){
        int a = 0, b = 0;
        rep(i, 0, N){
            if(sz(adj[i]) == 1) ++a;
            else if(sz(adj[i]) == N - 1) ++b;
            else return false;
        }
        return a == N - 1 && b == 1;
    }

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


        int mid = -1;
        rep(i, 0, N) if(sz(adj[i]) == N - 1) mid = i;

        for(auto u : idx){
            if(a[u] < b[u]){
                cout << 0 << '\n';
                return;
            }

            if(a[u] == b[u]) continue;

            rep(i, 0, N){
                if(a[i] == b[u]){
                    minimize(a[mid], a[i]);
                    minimize(a[u], a[mid]);
                    break;
                }
            }

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

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

        cout << 1 << '\n';
    }
}

namespace subtask2{
    bool check(){
        rep(i, 0, N){
            if(sz(adj[i]) != N - 1) return false;
        }
        return true;
    }

    void solve(){
        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]){
                cout << 0 << '\n';
                return;
            }

            bool found = false;
            rep(i, 0, N){
                if(a[i] == b[u]){
                    a[u] = b[u];
                    found = true;
                }
            }

            if(!found){
                cout << 0 << '\n';
                return;
            }
        }

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

        cout << 1 << '\n';
    }
}

namespace subtask3{
    bool check(){
        return true;
    }

    void solve(){
        cout << 0 << '\n';
    }
}

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;
        }
    }

    if(subtask1::check()) return subtask1::solve(), void();
    if(subtask2::check()) return subtask2::solve(), void();
    if(subtask3::check()) return subtask3::solve(), void();
}

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: 15 / 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