QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477881#997. 2-SAT 问题NOI_AK_ME#Compile Error//C++235.3kb2024-07-14 12:05:202024-07-14 12:05:21

Judging History

This is the latest submission verdict.

  • [2024-07-14 12:05:21]
  • Judged
  • [2024-07-14 12:05:20]
  • 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();
    return 0;

Details

answer.code: In function ‘int main()’:
answer.code:233:14: error: expected ‘}’ at end of input
  233 |     return 0;
      |              ^
answer.code:189:12: note: to match this ‘{’
  189 | int main() {
      |            ^
answer.code: In lambda function:
answer.code:16:18: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |             fread(buf_read, 1, buf_size, stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~