oj.uz

Submission #531360

# Submission time Handle Problem Language Result Execution time Memory
531360 2022-02-28T14:03:36 Z Lobo Colors (RMI18_colors) C++17
100 / 100
 826 ms 109188 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(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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18236 KB Output is correct
2 Correct 33 ms 18664 KB Output is correct
3 Correct 12 ms 18508 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 18476 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 18156 KB Output is correct
2 Correct 42 ms 18512 KB Output is correct
3 Correct 14 ms 18344 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 18156 KB Output is correct
2 Correct 42 ms 18512 KB Output is correct
3 Correct 14 ms 18344 KB Output is correct
4 Correct 146 ms 21064 KB Output is correct
5 Correct 471 ms 49612 KB Output is correct
6 Correct 797 ms 83564 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18236 KB Output is correct
2 Correct 33 ms 18664 KB Output is correct
3 Correct 12 ms 18508 KB Output is correct
4 Correct 98 ms 18156 KB Output is correct
5 Correct 42 ms 18512 KB Output is correct
6 Correct 14 ms 18344 KB Output is correct
7 Correct 72 ms 19500 KB Output is correct
8 Correct 44 ms 18552 KB Output is correct
9 Correct 16 ms 18372 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 18232 KB Output is correct
2 Correct 494 ms 51472 KB Output is correct
3 Correct 441 ms 60272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 18372 KB Output is correct
2 Correct 23 ms 19124 KB Output is correct
3 Correct 16 ms 18340 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18236 KB Output is correct
2 Correct 33 ms 18664 KB Output is correct
3 Correct 12 ms 18508 KB Output is correct
4 Correct 76 ms 18476 KB Output is correct
5 Correct 98 ms 18156 KB Output is correct
6 Correct 42 ms 18512 KB Output is correct
7 Correct 14 ms 18344 KB Output is correct
8 Correct 146 ms 21064 KB Output is correct
9 Correct 471 ms 49612 KB Output is correct
10 Correct 797 ms 83564 KB Output is correct
11 Correct 72 ms 19500 KB Output is correct
12 Correct 44 ms 18552 KB Output is correct
13 Correct 16 ms 18372 KB Output is correct
14 Correct 143 ms 18232 KB Output is correct
15 Correct 494 ms 51472 KB Output is correct
16 Correct 441 ms 60272 KB Output is correct
17 Correct 42 ms 18372 KB Output is correct
18 Correct 23 ms 19124 KB Output is correct
19 Correct 16 ms 18340 KB Output is correct
20 Correct 129 ms 20996 KB Output is correct
21 Correct 446 ms 55468 KB Output is correct
22 Correct 826 ms 109188 KB Output is correct