oj.uz

Submission #198425

# Submission time Handle Problem Language Result Execution time Memory
198425 2020-01-26T02:36:02 Z model_code Colors (RMI18_colors) C++14
100 / 100
 1126 ms 75720 KB 
// Author: Ștefan Constantin-Buliga
#include <cstring>
#include <fstream>
#include <vector>

using namespace std;

const int SIZE = 1 << 10;

int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0;
    char ch = Advance();
    while (!isdigit(ch))
        ch = Advance();
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer;
}

const int MAXN = 150000;
const int MAXM = 200000;

int before[1 + MAXN], after[1 + MAXN];
vector<int> hereBefore[1 + MAXN], hereAfter[1 + MAXN];
vector<pair<int, int> > tree[1 + 4 * MAXN];
bool seen[1 + MAXN], bad;
int weight[1 + MAXN], dad[1 + MAXN];

void Add(int node, int left, int right, int from, int to, int a, int b) {
    if (from <= left && right <= to) {
        tree[node].push_back(make_pair(a, b));
        return;
    }
    int middle = (left + right) / 2;
    if (from <= middle)
        Add(2 * node, left, middle, from, to, a, b);
    if (middle + 1 <= to)
        Add(2 * node + 1, middle + 1, right, from, to, a, b);
}

void Initialize(int n) {
    for (int i = 1; i <= n; i++) {
        dad[i] = i;
        weight[i] = 1;
    }
}

struct Change {
    int when;
    int node;
    bool type;
    int before;
};

vector<Change> Stack;

int FindDad(int node) {
    while (dad[node] != node)
        node = dad[node];
    return node;
}

void AddEdge(int a, int b, int id) {
    a = FindDad(a);
    b = FindDad(b);
    if (a == b)
        return;
    if (weight[a] <= weight[b]) {
        Stack.push_back({id, a, false, dad[a]});
        dad[a] = b;
        Stack.push_back({id, b, true, weight[b]});
        weight[b] += weight[a];
    }
    else {
        Stack.push_back({id, b, false, dad[b]});
        dad[b] = a;
        Stack.push_back({id, a, true, weight[a]});
        weight[a] += weight[b];
    }
}

void Undo(int id) {
    while (!Stack.empty() && Stack.back().when == id) {
        if (Stack.back().type)
            weight[Stack.back().node] = Stack.back().before;
        else
            dad[Stack.back().node] = Stack.back().before;
        Stack.pop_back();
    }
}

int number = 0;
int last[1 + MAXN];

void Solve(int node, int left, int right) {
    for (auto &it : tree[node])
        AddEdge(it.first, it.second, node);
    tree[node].clear();
    if (left == right) {
        number++;
        for (auto &it : hereBefore[left])
            last[FindDad(it)] = number;
        for (auto &it : hereAfter[left])
            if (last[FindDad(it)] != number)
                bad = true;
    }
    else {
        int middle = (left + right) / 2;
        Solve(2 * node, left, middle);
        Solve(2 * node + 1, middle + 1, right);
    }
    Undo(node);
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    int tests = Read();
    for (int test = 1; test <= tests; test++) {
        int n = Read(), m = Read();
        memset(seen, false, sizeof(seen));
        for (int i = 1; i <= n; i++) {
            hereBefore[i].clear();
            hereAfter[i].clear();
        }
        for (int i = 1; i <= n; i++) {
            before[i] = Read();
            hereBefore[before[i]].push_back(i);
            seen[before[i]] = true;
        }
        bad = false;
        for (int i = 1; i <= n; i++) {
            after[i] = Read();
            hereAfter[after[i]].push_back(i);
            if (after[i] > before[i] || !seen[after[i]])
                bad = true;
        }
        if (n == 1) {
            printf("1\n");
            continue;
        }
        for (int i = 1; i <= m; i++) {
            int a = Read(), b = Read();
            int from = max(after[a], after[b]), to = min(before[a], before[b]);
            if (from <= to && !bad)
                Add(1, 1, n, from, to, a, b);
        }
        if (bad) {
            printf("0\n");
            continue;
        }
        Initialize(n);
        number = 0;
        memset(last, 0, sizeof(last));
        Solve(1, 1, n);
        if (bad)
            printf("0\n");
        else
            printf("1\n");
    }
    return 0;
}

Compilation message

colors.cpp: In function 'char Advance()':
colors.cpp:15:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buffer, 1, SIZE, stdin);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 22392 KB Output is correct
2 Correct 45 ms 22264 KB Output is correct
3 Correct 23 ms 22520 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22392 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 22376 KB Output is correct
2 Correct 48 ms 22264 KB Output is correct
3 Correct 23 ms 22396 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 22376 KB Output is correct
2 Correct 48 ms 22264 KB Output is correct
3 Correct 23 ms 22396 KB Output is correct
4 Correct 281 ms 22264 KB Output is correct
5 Correct 598 ms 38468 KB Output is correct
6 Correct 1126 ms 59440 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 22392 KB Output is correct
2 Correct 45 ms 22264 KB Output is correct
3 Correct 23 ms 22520 KB Output is correct
4 Correct 195 ms 22376 KB Output is correct
5 Correct 48 ms 22264 KB Output is correct
6 Correct 23 ms 22396 KB Output is correct
7 Correct 184 ms 22264 KB Output is correct
8 Correct 49 ms 22264 KB Output is correct
9 Correct 25 ms 22520 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 22396 KB Output is correct
2 Correct 546 ms 40176 KB Output is correct
3 Correct 554 ms 49300 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22264 KB Output is correct
2 Correct 29 ms 22648 KB Output is correct
3 Correct 23 ms 22392 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 22392 KB Output is correct
2 Correct 45 ms 22264 KB Output is correct
3 Correct 23 ms 22520 KB Output is correct
4 Correct 71 ms 22392 KB Output is correct
5 Correct 195 ms 22376 KB Output is correct
6 Correct 48 ms 22264 KB Output is correct
7 Correct 23 ms 22396 KB Output is correct
8 Correct 281 ms 22264 KB Output is correct
9 Correct 598 ms 38468 KB Output is correct
10 Correct 1126 ms 59440 KB Output is correct
11 Correct 184 ms 22264 KB Output is correct
12 Correct 49 ms 22264 KB Output is correct
13 Correct 25 ms 22520 KB Output is correct
14 Correct 279 ms 22396 KB Output is correct
15 Correct 546 ms 40176 KB Output is correct
16 Correct 554 ms 49300 KB Output is correct
17 Correct 51 ms 22264 KB Output is correct
18 Correct 29 ms 22648 KB Output is correct
19 Correct 23 ms 22392 KB Output is correct
20 Correct 82 ms 22520 KB Output is correct
21 Correct 498 ms 42844 KB Output is correct
22 Correct 927 ms 75720 KB Output is correct