oj.uz

Submission #531361

# Submission time Handle Problem Language Result Execution time Memory
531361 2022-02-28T14:04:31 Z Lobo Colors (RMI18_colors) C++17
100 / 100
 651 ms 63532 KB 
#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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 17988 KB Output is correct
2 Correct 28 ms 18056 KB Output is correct
3 Correct 12 ms 18252 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 18100 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17980 KB Output is correct
2 Correct 30 ms 17996 KB Output is correct
3 Correct 13 ms 18124 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17980 KB Output is correct
2 Correct 30 ms 17996 KB Output is correct
3 Correct 13 ms 18124 KB Output is correct
4 Correct 138 ms 17988 KB Output is correct
5 Correct 386 ms 32032 KB Output is correct
6 Correct 651 ms 49100 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 17988 KB Output is correct
2 Correct 28 ms 18056 KB Output is correct
3 Correct 12 ms 18252 KB Output is correct
4 Correct 66 ms 17980 KB Output is correct
5 Correct 30 ms 17996 KB Output is correct
6 Correct 13 ms 18124 KB Output is correct
7 Correct 63 ms 17980 KB Output is correct
8 Correct 29 ms 18012 KB Output is correct
9 Correct 13 ms 18124 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 18012 KB Output is correct
2 Correct 380 ms 33116 KB Output is correct
3 Correct 355 ms 39552 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18052 KB Output is correct
2 Correct 20 ms 18336 KB Output is correct
3 Correct 13 ms 18124 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 17988 KB Output is correct
2 Correct 28 ms 18056 KB Output is correct
3 Correct 12 ms 18252 KB Output is correct
4 Correct 75 ms 18100 KB Output is correct
5 Correct 66 ms 17980 KB Output is correct
6 Correct 30 ms 17996 KB Output is correct
7 Correct 13 ms 18124 KB Output is correct
8 Correct 138 ms 17988 KB Output is correct
9 Correct 386 ms 32032 KB Output is correct
10 Correct 651 ms 49100 KB Output is correct
11 Correct 63 ms 17980 KB Output is correct
12 Correct 29 ms 18012 KB Output is correct
13 Correct 13 ms 18124 KB Output is correct
14 Correct 144 ms 18012 KB Output is correct
15 Correct 380 ms 33116 KB Output is correct
16 Correct 355 ms 39552 KB Output is correct
17 Correct 37 ms 18052 KB Output is correct
18 Correct 20 ms 18336 KB Output is correct
19 Correct 13 ms 18124 KB Output is correct
20 Correct 94 ms 18348 KB Output is correct
21 Correct 356 ms 35464 KB Output is correct
22 Correct 627 ms 63532 KB Output is correct