Submission #198425

#	Time	Username	Problem	Language	Result	Execution time	Memory
198425		model_code	Colors (RMI18_colors)	C++14	100 / 100	1126 ms	75720 KiB

colors

// 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 (stderr)

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 / 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