oj.uz

Submission #375088

# Submission time Handle Problem Language Result Execution time Memory
375088 2021-03-09T02:28:47 Z ijxjdjd Colors (RMI18_colors) C++14
100 / 100
 884 ms 63324 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = (int)(150000) + 5;
int timer = 5;

int N, M;

int a[MAXN];
int b[MAXN];

int par[MAXN];
int rk[MAXN];

int cur[MAXN];

pair<int, int> edges[MAXN + 50000];
vector<int> A[MAXN];
vector<int> B[MAXN];

deque<pair<int, int>> last;

vector<int> seg[4*MAXN];

bool good = true;

int find(int x) {
    if (par[x] == x) {
        return x;
    }
    else {
        return find(par[x]);
    }
}
void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
        if (rk[px] < rk[py]) {
            swap(px, py);
        }
        rk[px] += rk[py];
        par[py] = px;
        last.push_back({px, py});
    }
    else {
        last.push_back({-1, -1});
    }
}
void add(int l, int r, int i, int n = 1, int tl = 0, int tr = N-1) {
    if (l > tr || r < tl) {
        return;
    }
    else if (l <= tl && tr <= r) {
        seg[n].push_back(i);
    }
    else {
        int tm = (tl + tr)/2;
        add(l, r, i, 2*n, tl, tm);
        add(l, r, i, 2*n+1, tm+1, tr);
    }
}
void undo() {
    auto lst = last.back();
    last.pop_back();
    if (lst.first != -1) {
        rk[lst.first] -= rk[lst.second];
        par[lst.second] = lst.second;
    }
}
void go(int n = 1, int tl = 0, int tr = N-1) {
    for (int e : seg[n]) {
        merge(edges[e].first, edges[e].second);
    }
    if (tl == tr) {
        timer++;
        for (int ai : A[tl]) {
            cur[find(ai)] = timer;
        }
        for (int bi : B[tl]) {
            if (cur[find(bi)] != timer) {
                good = false;
            }
        }
    }
    else {
        int tm = (tl + tr)/2;
        go(2*n, tl, tm);
        go(2*n+1, tm+1, tr);
    }
    FR(iter, seg[n].size()) {
        undo();
    }
}

void reset() {
    good = true;
    assert (last.size() == 0);
    FR(i, N) {
        par[i] = i;
        rk[i] = 1;
        A[i].clear();
        B[i].clear();
    }
    FR(i, 4*N) {
        seg[i].clear();
    }
}
int solve() {
    cin >> N >> M;
    reset();
    FR(i, N) {
        cin >> a[i];
        a[i]--;
        A[a[i]].push_back(i);
    }
    FR(i, N) {
        cin >> b[i];
        b[i]--;
        B[b[i]].push_back(i);
    }
    for (int i = 0; i < M; i++) {
        cin >> edges[i].first >> edges[i].second;
        edges[i].first--;
        edges[i].second--;
        int a1 = a[edges[i].first];
        int b1 = b[edges[i].first];
        int a2 = a[edges[i].second];
        int b2 = b[edges[i].second];
        add(max(b1, b2), min(a1, a2), i);
    }
    go();
    return good;
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
    int T;
    cin >> T;
    while (T-->0) {
        cout << solve() << '\n';
    }
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21484 KB Output is correct
2 Correct 40 ms 21612 KB Output is correct
3 Correct 18 ms 21868 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 21612 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21484 KB Output is correct
2 Correct 45 ms 22124 KB Output is correct
3 Correct 19 ms 21868 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21484 KB Output is correct
2 Correct 45 ms 22124 KB Output is correct
3 Correct 19 ms 21868 KB Output is correct
4 Correct 163 ms 21720 KB Output is correct
5 Correct 519 ms 37272 KB Output is correct
6 Correct 884 ms 54232 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21484 KB Output is correct
2 Correct 40 ms 21612 KB Output is correct
3 Correct 18 ms 21868 KB Output is correct
4 Correct 84 ms 21484 KB Output is correct
5 Correct 45 ms 22124 KB Output is correct
6 Correct 19 ms 21868 KB Output is correct
7 Correct 84 ms 21484 KB Output is correct
8 Correct 41 ms 21612 KB Output is correct
9 Correct 19 ms 21740 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 21612 KB Output is correct
2 Correct 497 ms 38580 KB Output is correct
3 Correct 501 ms 50792 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 21740 KB Output is correct
2 Correct 28 ms 21868 KB Output is correct
3 Correct 20 ms 21612 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21484 KB Output is correct
2 Correct 40 ms 21612 KB Output is correct
3 Correct 18 ms 21868 KB Output is correct
4 Correct 89 ms 21612 KB Output is correct
5 Correct 84 ms 21484 KB Output is correct
6 Correct 45 ms 22124 KB Output is correct
7 Correct 19 ms 21868 KB Output is correct
8 Correct 163 ms 21720 KB Output is correct
9 Correct 519 ms 37272 KB Output is correct
10 Correct 884 ms 54232 KB Output is correct
11 Correct 84 ms 21484 KB Output is correct
12 Correct 41 ms 21612 KB Output is correct
13 Correct 19 ms 21740 KB Output is correct
14 Correct 153 ms 21612 KB Output is correct
15 Correct 497 ms 38580 KB Output is correct
16 Correct 501 ms 50792 KB Output is correct
17 Correct 53 ms 21740 KB Output is correct
18 Correct 28 ms 21868 KB Output is correct
19 Correct 20 ms 21612 KB Output is correct
20 Correct 124 ms 24172 KB Output is correct
21 Correct 491 ms 41496 KB Output is correct
22 Correct 841 ms 63324 KB Output is correct