QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#81654#1. I/O Testjrjyy0 0ms0kbC++147.8kb2023-02-25 19:06:112023-02-25 19:06:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-25 19:06:13]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2023-02-25 19:06:11]
  • 提交

config.txt

0 0
文本文件

input_test

/* FILENAME */
#include <bits/stdc++.h>

#define fo(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout);
#define rep(i, l, r) for (int i = (l), rep##i = (r); i <= rep##i; ++i)
#define per(i, r, l) for (int i = (r), per##i = (l); i >= per##i; --i)
#define r0p(i, r) rep (i, 0, (r) - 1)
#define p0r(i, l) per (i, (l) - 1, 0)
#define each(x, s) for (auto &x : (s))
#define all(s) (s).begin(), (s).end()
#define dbg(x) (cerr << "Line#" << __LINE__ << " " << #x << "=" << (x) << endl)

using ll = long long; using ull = unsigned long long;
template <class T> using vec = std::vector<T>; using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int K = 25;

struct Edge { int to, nx; };
Edge E[maxn * 2]; int H[maxn], tt;
#define foe(v, u) for (int ei##v = H[u], v; v = E[ei##v].to, ei##v; ei##v = E[ei##v].nx)
void add(int u, int v) { E[++tt] = {v, H[u]}, H[u] = tt; }
void Add(int u, int v) { add(u, v), add(v, u); }
// vec<int> G[maxn];
// void Add(int u, int v) { G[u].push_back(v), G[v].push_back(u); }
// #define foe(v, u) each (v, G[u])

int n, c[maxn]; bool a[maxn], b[maxn];

int val(int i, int p) { return (c[i] >> p) & 1; }

struct Data {
    int a[2][2][3];
    Data() { r0p (i, 2) r0p (j, 2) r0p (k, 3) a[i][j][k] = 0; }
    auto operator[](std::size_t p) { return a[p]; }
    const auto operator[](std::size_t p) const { return a[p]; }
    Data &operator+=(const Data &y) {
        r0p (i, 2) r0p (j, 2) r0p (k, 3) a[i][j][k] += y[i][j][k];
        return *this;
    }
    Data &operator-=(const Data &y) {
        r0p (i, 2) r0p (j, 2) r0p (k, 3) a[i][j][k] -= y[i][j][k];
        return *this;
    }
    void add(const Data &y, bool p, bool q) {
        // assert(0 <= p && p < 2 && 0 <= q && q < 2);
#define Upd(c, o, p, q) a[i c p][j c q][o] += y[i][j][o]
        // r0p (i, 2) r0p (j, 2) Upd(&, 0, p, q), Upd(|, 1, p, q), Upd(^, 2, p, q);
#define Fuck(n, m) if (p == n && q == m) { \
    r0p (i, 2) r0p (j, 2) Upd(&, 0, n, m), Upd(|, 1, n, m), Upd(^, 2, n, m); \
}
        Fuck(0, 0)
        else Fuck(0, 1)
        else Fuck(1, 0)
        else Fuck(1, 1)
#undef Upd
    }
    void del(const Data &y, bool p, bool q) {
        // assert(0 <= p && p < 2 && 0 <= q && q < 2);
#define Upd(c, o, p, q) a[i c p][j c q][o] -= y[i][j][o]
        // r0p (i, 2) r0p (j, 2) Upd(&, 0, p, q), Upd(|, 1, p, q), Upd(^, 2, p, q);
#define Fuck(n, m) if (p == n && q == m) { \
    r0p (i, 2) r0p (j, 2) Upd(&, 0, n, m), Upd(|, 1, n, m), Upd(^, 2, n, m); \
}
        Fuck(0, 0)
        else Fuck(0, 1)
        else Fuck(1, 0)
        else Fuck(1, 1)
#undef Upd
    }
    void st(int p, int q) { r0p (k, 3) a[p][q][k] = 1; }
};

Data f[maxn];
ll A[3], B[3];

int p, q;

void dfs(int u, int fa) {
    f[u].st(a[u], b[u]);
    foe (v, u) if (v != fa) {
        dfs(v, u);
        f[u].add(f[v], a[u], b[u]);
    }
}
void dfs2(int u, int fa) {
    r0p (k, 3) A[k] += f[u][1][1][k];
    foe (v, u) if (v != fa) {
        Data F = f[u]; F.del(f[v], a[u], b[u]);
        f[v].add(F, a[v], b[v]);
        dfs2(v, u);
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef DEBUG
    cin >> n;
    rep (i, 1, n) cin >> c[i];
    r0p (_, n - 1) { int u, v; cin >> u >> v, Add(u, v); }
#else
    n = 100000; mt19937 rnd(114514);
    rep (i, 1, n) c[i] = 1;
    rep (u, 2, n) Add(u - 1, u);
#endif
    // rep (i, 1, n) c[i] = rnd() & ((1 << K) - 1);
    // rep (u, 2, n) Add(rnd() % (u - 1) + 1, u);

    r0p (p, K) r0p (q, p + 1) {
        ::p = p, ::q = q;
        fill(f + 1, f + n + 1, Data());
        rep (i, 1, n) a[i] = val(i, p), b[i] = val(i, q);
        r0p (k, 3) A[k] = 0;
        dfs(1, -1), dfs2(1, -1);
        if (p != q) r0p (k, 3) A[k] *= 2;
        r0p (k, 3) (B[k] += (1ll << (p + q)) % P * (A[k] % P) % P) %= P;
    }
    r0p (k, 3) cout << B[k] << ' ';
    cerr << "\n" << double(clock()) / CLOCKS_PER_SEC << "s\n";
    return 0;
}
源文件, 语言: C++14

output_test

/* FILENAME */
#include <bits/stdc++.h>

#define fo(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout);
#define rep(i, l, r) for (int i = (l), rep##i = (r); i <= rep##i; ++i)
#define per(i, r, l) for (int i = (r), per##i = (l); i >= per##i; --i)
#define r0p(i, r) rep (i, 0, (r) - 1)
#define p0r(i, l) per (i, (l) - 1, 0)
#define each(x, s) for (auto &x : (s))
#define all(s) (s).begin(), (s).end()
#define dbg(x) (cerr << "Line#" << __LINE__ << " " << #x << "=" << (x) << endl)

using ll = long long; using ull = unsigned long long;
template <class T> using vec = std::vector<T>; using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int K = 25;

struct Edge { int to, nx; };
Edge E[maxn * 2]; int H[maxn], tt;
#define foe(v, u) for (int ei##v = H[u], v; v = E[ei##v].to, ei##v; ei##v = E[ei##v].nx)
void add(int u, int v) { E[++tt] = {v, H[u]}, H[u] = tt; }
void Add(int u, int v) { add(u, v), add(v, u); }
// vec<int> G[maxn];
// void Add(int u, int v) { G[u].push_back(v), G[v].push_back(u); }
// #define foe(v, u) each (v, G[u])

int n, c[maxn]; bool a[maxn], b[maxn];

int val(int i, int p) { return (c[i] >> p) & 1; }

struct Data {
    int a[2][2][3];
    Data() { r0p (i, 2) r0p (j, 2) r0p (k, 3) a[i][j][k] = 0; }
    auto operator[](std::size_t p) { return a[p]; }
    const auto operator[](std::size_t p) const { return a[p]; }
    Data &operator+=(const Data &y) {
        r0p (i, 2) r0p (j, 2) r0p (k, 3) a[i][j][k] += y[i][j][k];
        return *this;
    }
    Data &operator-=(const Data &y) {
        r0p (i, 2) r0p (j, 2) r0p (k, 3) a[i][j][k] -= y[i][j][k];
        return *this;
    }
    void add(const Data &y, bool p, bool q) {
        // assert(0 <= p && p < 2 && 0 <= q && q < 2);
#define Upd(c, o, p, q) a[i c p][j c q][o] += y[i][j][o]
        // r0p (i, 2) r0p (j, 2) Upd(&, 0, p, q), Upd(|, 1, p, q), Upd(^, 2, p, q);
#define Fuck(n, m) if (p == n && q == m) { \
    r0p (i, 2) r0p (j, 2) Upd(&, 0, n, m), Upd(|, 1, n, m), Upd(^, 2, n, m); \
}
        Fuck(0, 0)
        else Fuck(0, 1)
        else Fuck(1, 0)
        else Fuck(1, 1)
#undef Upd
    }
    void del(const Data &y, bool p, bool q) {
        // assert(0 <= p && p < 2 && 0 <= q && q < 2);
#define Upd(c, o, p, q) a[i c p][j c q][o] -= y[i][j][o]
        // r0p (i, 2) r0p (j, 2) Upd(&, 0, p, q), Upd(|, 1, p, q), Upd(^, 2, p, q);
#define Fuck(n, m) if (p == n && q == m) { \
    r0p (i, 2) r0p (j, 2) Upd(&, 0, n, m), Upd(|, 1, n, m), Upd(^, 2, n, m); \
}
        Fuck(0, 0)
        else Fuck(0, 1)
        else Fuck(1, 0)
        else Fuck(1, 1)
#undef Upd
    }
    void st(int p, int q) { r0p (k, 3) a[p][q][k] = 1; }
};

Data f[maxn];
ll A[3], B[3];

int p, q;

void dfs(int u, int fa) {
    f[u].st(a[u], b[u]);
    foe (v, u) if (v != fa) {
        dfs(v, u);
        f[u].add(f[v], a[u], b[u]);
    }
}
void dfs2(int u, int fa) {
    r0p (k, 3) A[k] += f[u][1][1][k];
    foe (v, u) if (v != fa) {
        Data F = f[u]; F.del(f[v], a[u], b[u]);
        f[v].add(F, a[v], b[v]);
        dfs2(v, u);
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef DEBUG
    cin >> n;
    rep (i, 1, n) cin >> c[i];
    r0p (_, n - 1) { int u, v; cin >> u >> v, Add(u, v); }
#else
    n = 100000; mt19937 rnd(114514);
    rep (i, 1, n) c[i] = 1;
    rep (u, 2, n) Add(u - 1, u);
#endif
    // rep (i, 1, n) c[i] = rnd() & ((1 << K) - 1);
    // rep (u, 2, n) Add(rnd() % (u - 1) + 1, u);

    r0p (p, K) r0p (q, p + 1) {
        ::p = p, ::q = q;
        fill(f + 1, f + n + 1, Data());
        rep (i, 1, n) a[i] = val(i, p), b[i] = val(i, q);
        r0p (k, 3) A[k] = 0;
        dfs(1, -1), dfs2(1, -1);
        if (p != q) r0p (k, 3) A[k] *= 2;
        r0p (k, 3) (B[k] += (1ll << (p + q)) % P * (A[k] % P) % P) %= P;
    }
    r0p (k, 3) cout << B[k] << ' ';
    cerr << "\n" << double(clock()) / CLOCKS_PER_SEC << "s\n";
    return 0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 0
Skipped

Subtask #2:

score: 0
Skipped
English 繁體中文 简体中文

服务器时间: 2025-01-21 15:45:50 | 开源项目