QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#477882#997. 2-SAT 问题NOI_AK_ME#RE 0ms0kbC++235.3kb2024-07-14 12:05:482024-07-14 12:05:48

Judging History

This is the latest submission verdict.

  • [2024-07-14 12:05:48]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-07-14 12:05:48]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

namespace fastio {

const int buf_size = 1 << 14;
char buf_read[buf_size];
char buf_write[buf_size + 30];
char *ptr_read = buf_read + buf_size;
char *ptr_write = buf_write;

long long read_int() {
    auto getChar = []() {
        if (ptr_read == buf_read + buf_size){
            fread(buf_read, 1, buf_size, stdin);
            ptr_read = buf_read;
        }
        return *ptr_read++;
    };
    char c = getChar();
    while (c && (c < '0' || c > '9') && c != '-') {
        c = getChar();
    }
    long long z = 1;
    if (c == '-') {
        z = -1;
        c = getChar();
    }
    long long res = 0;
    while (c >= '0' && c <= '9'){
        res = res * 10 + (c - '0');
        c = getChar();
    }
    return z * res;
}

void write_flush() {
    fwrite(buf_write, 1, ptr_write - buf_write, stdout);
    ptr_write = buf_write;
}

void write_int(long long x) {
    if (x < 0) {
        *ptr_write++ = '-';
        x = -x;
    }
    char *start = ptr_write;
    if (!x) {
        *ptr_write++ = '0';
    }
    while (x) {
        *ptr_write++ = x % 10 + '0';
        x /= 10;
    }
    reverse(start, ptr_write);
    if (ptr_write >= buf_write + buf_size) {
        write_flush();
    }
}

void write_char(char c) {
    *ptr_write++ = c;
    if (ptr_write >= buf_write + buf_size) {
        write_flush();
    }
}

void write_string(const string &s) {
    for (char c : s) {
        write_char(c);
    }
}

}

template<typename Edge>
class GraphIterator {
public:
    class OutgoingEdges {
    public:
        OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) {
        }

        const Edge* begin() const {
            if (l == r) {
                return 0;
            }
            return &g->prepared_edges[l];
        }

        const Edge* end() const {
            if (l == r) {
                return 0;
            }
            return &g->prepared_edges[r];
        }

    private:
        int l, r;
        const GraphIterator *g;
    };

    void add_edge(int from, const Edge &e) {
        edges.push_back({from, e});
    }

    void prepare() {
        int n = 0;
        for (const auto &e : edges) {
            n = max(n, e.first);
        }
        n += 2;
        start.resize(n);
        for (const auto &e : edges) {
            ++start[e.first + 1];
        }
        for (int i = 1; i < n; ++i) {
            start[i] += start[i - 1];
        }
        prepared_edges.resize(edges.size() + 1);
        auto counter = start;
        for (const auto &e : edges) {
            prepared_edges[counter[e.first]++] = e.second;
        }
    }

    OutgoingEdges operator [] (int from) const {
        if (from < 0 || from + 1 >= start.size()) {
            return {this, 0, 0};
        }
        return {this, start[from], start[from + 1]};
    }

private:
    vector<Edge> prepared_edges;
    vector<pair<int, Edge>> edges;
    vector<int> start;
};

class two_sat {
public:
    two_sat(int n): answer(n, -1) {
    }

    void add_or_clause(int x, bool valx, int y, bool valy) {
        x = x * 2 + valx;
        y = y * 2 + valy;
        g.add_edge(x ^ 1, y);
        g.add_edge(y ^ 1, x);
    }

    pair<bool, vector<int>> solve() {
        g.prepare();
        for (int i = 0; i < answer.size(); ++i) {
            if (answer[i] == -1) {
                lastv.clear();
                if (!dfs(2 * i)) {
                    for (int v : lastv) {
                        answer[v] = -1;
                    }
                    if (!dfs(2 * i + 1)) {
                        return {false, {}};
                    }
                }
            }
        }
        return {true, answer};
    }

private:
    bool dfs(int v) {
        lastv.push_back(v / 2);
        answer[v / 2] = v % 2;
        for (int to : g[v]) {
            if ((answer[to / 2] != -1 && answer[to / 2] != to % 2) || (answer[to / 2] == -1 && !dfs(to))) {
                return false;
            }
        }
        return true;
    }

    vector<int> answer, lastv;
    GraphIterator<int> g;
};

int n, m;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    /*GraphIterator<int> g;
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    g.add_edge(0, 2);
    g.prepare();
    for (int i = -1230; i < 512; ++i) {
        for (const auto &e : g[i]) {
            cout << i << " -> " << e << endl;
        }
    }
    return 0;*/
    n = fastio::read_int();
    m = fastio::read_int();
    two_sat ts(n);
    while (m--) {
        int a, c, x;
        a = fastio::read_int();
        c = fastio::read_int();
        x = fastio::read_int();
        bool b = a > 0;
        bool d = c > 0;
        a = abs(a) - 1;
        c = abs(c) - 1;
        ts.add_or_clause(a, b, c, d);
    }
    auto ans = ts.solve();
    if (ans.first) {
        fastio::write_string("Yes\n");
        for (int i = 0; i < n; ++i) {
            int x = i + 1;
            if (!ans.second[i]) {
                x = -x;
            }
            fastio::write_int(x);
            fastio::write_char(' ');
        }
        fastio::write_string("0\n");
    } else {
        fastio::write_string("No");
    }
    fastio::write_flush();
}

详细

Test #1:

score: 0
Runtime Error

input:

86354 86418
14615 0 14903 1
13605 0 4458 0
15604 0 77112 0
52311 1 64996 0
22711 1 74245 1
39042 1 57372 1
2994 1 84183 1
80574 0 58791 1
27780 1 9336 1
61809 0 7216 0
71113 0 42287 1
20073 0 72448 0
73840 0 77048 0
28955 0 4165 0
16322 1 14075 1
43512 0 58600 1
45219 0 53858 0
14919 0 22576 0
16594...

output:


result: