Submission #531360

#	Time	Username	Problem	Language	Result	Execution time	Memory
531360		Lobo	Colors (RMI18_colors)	C++17	100 / 100	826 ms	109188 KiB

colors

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 150100

int n, m, a[maxn], b[maxn], ans;
int ds[maxn], dsz[maxn], dsc[maxn];
vector<int> idb[maxn];
vector<pair<int,int>> tr[4*maxn];
stack<pair<pair<int,int>,int>> rlb;

int find(int u) {
    if(u == ds[u]) return u;
    return find(ds[u]);
}

void join(int u, int v) {
    if(dsz[u] < dsz[v]) swap(u,v);
    if(u == v) {
        rlb.push(mp(mp(-1,-1),-1));
        return;
    }
    rlb.push(mp(mp(u,v),dsc[u]));
    dsz[u]+= dsz[v];
    ds[v] = u;
    dsc[u] = min(dsc[u],dsc[v]);
}

void rollback() {
    int u = rlb.top().fr.fr;
    int v = rlb.top().fr.sc;
    int dscant = rlb.top().sc;
    rlb.pop();
    if(u == -1) return;

    dsz[u]-= dsz[v];
    ds[v] = v;
    dsc[u] = dscant;
}

void att(int no, int l, int r, int L, int R, int u, int v) {
    if(l > R || r < L) return;
    else if(l >= L && r <= R) {
        tr[no].pb(mp(u,v));
    }
    else {
        int f1 = 2*no;
        int f2 = 2*no+1;
        int mid = (l+r)/2;

        att(f1,l,mid,L,R,u,v);
        att(f2,mid+1,r,L,R,u,v);
    }
}

void qrr(int no, int l, int r) {
    for(auto X : tr[no]) {
        int u = X.fr;
        int v = X.sc;
        u = find(u);
        v = find(v);
        join(u,v);
    }

    if(l == r) {
        for(auto u : idb[l]) {
            int pu = find(u);
            if(dsc[pu] != b[u]) {
                ans = 0;
            }
        }
    }

    if(l != r) {
        int f1 = 2*no;
        int f2 = 2*no+1;
        int mid = (l+r)/2;

        qrr(f1,l,mid);
        qrr(f2,mid+1,r);
    }

    for(int i = 0; i < tr[no].size(); i++) {
        rollback();
    }
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) idb[i].clear();
    for(int i = 1; i <= 4*n; i++) tr[i].clear();
    ans = 1;

    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
        idb[b[i]].pb(i);
    }

    for(int i = 1; i <= n; i++) {
        ds[i] = i;
        dsz[i] = 1;
        dsc[i] = a[i];
    }

    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        int l = max(b[u],b[v]);
        int r = min(a[u],a[v]);
        if(l > r) continue;
        att(1,1,n,l,r,u,v);
    }

    qrr(1,1,n);
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    cin >> tt;
    while(tt--) solve();

}

Compilation message (stderr)

colors.cpp: In function 'void qrr(long long int, long long int, long long int)':
colors.cpp:94:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < tr[no].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22