제출 #1266991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266991		ducdev	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	45 ms	10856 KiB

election_campaign

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_N = 1e5;
const int MOD = 1e9 + 7;

struct Query {
    int u, v, w;
    Query() {};
    Query(int u, int v, int w) : u(u), v(v), w(w) {};
};

struct FenwickTree {
    int n;
    vector<int> bit;

    void update(int pos, int val) {
        for (; pos <= n; pos += pos & (-pos))
            bit[pos] += val;
    };

    int get(int pos) {
        int ret = 0;
        for (; pos > 0; pos -= pos & (-pos))
            ret += bit[pos];
        return ret;
    };

    void update(int l, int r, int val) {
        update(l, val);
        update(r, -val);
    };

    FenwickTree(int n) : n(n) {
        bit.assign(n + 5, 0);
    };
};

int n, q, timer, lg;
int tin[MAX_N + 5], tout[MAX_N + 5], up[MAX_N + 5][18], depth[MAX_N + 5];
vector<int> adj[MAX_N + 5];
vector<Query> queries;

void preDfs(int u, int par) {
    tin[u] = ++timer;
    up[u][0] = par;
    depth[u] = depth[par] + 1;

    for (int i = 1; i <= lg; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : adj[u]) {
        if (v == par) continue;
        preDfs(v, u);
    };

    tout[u] = ++timer;
};

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
};

int __lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;

    for (int i = lg; i >= 0; i--)
        if (!isAncestor(up[u][i], v))
            u = up[u][i];

    return up[u][0];
};

int kthAnc(int u, int k) {
    for (int i = lg; i >= 0; i--)
        if (k >> i & 1) u = up[u][i];
    return u;
};

void constructLCA() {
    lg = ceil(log2(n));
    preDfs(1, 1);
};

namespace SUBTASK_1 {
    const int N = MAX_N;
    const int Q = 15;

    void Solve() {
        constructLCA();

        FenwickTree bit(timer);

        int res = 0;
        for (int mask = 0; mask < (1 << q); mask++) {
            bool valid = true;

            int sum = 0;
            int realMask = 0;
            for (int i = 0; i < q; i++) {
                if (mask >> i & 1) {
                    int u = queries[i].u, v = queries[i].v, w = queries[i].w;

                    if (bit.get(tin[u]) + bit.get(tin[v]) - 2 * bit.get(tin[__lca(u, v)]) > 0) {
                        valid = false;
                        break;
                    };

                    sum += w;
                    bit.update(tin[u], tout[u], 1);
                    bit.update(tin[v], tout[v], 1);
                    realMask |= 1 << i;
                };
                if (!valid) break;
            };

            if (valid) res = max(res, sum);

            for (int i = 0; i < q; i++) {
                if (realMask >> i & 1) {
                    int u = queries[i].u, v = queries[i].v, w = queries[i].w;
                    bit.update(tin[u], tout[u], -1);
                    bit.update(tin[v], tout[v], -1);
                };
            };
        };

        cout << res << '\n';
    };
};  // namespace SUBTASK_1

namespace SUBTASK_23 {
    const int N = MAX_N;

    int dp[N + 5];
    vector<int> camp[N + 5];

    bool checkSubtask() {
        for (int u = 1; u <= n; u++)
            if (adj[u].size() > 2) return false;
        return true;
    };

    void Solve() {
        for (int i = 0; i < q; i++) {
            int &u = queries[i].u, &v = queries[i].v;
            if (u < v) swap(u, v);
            camp[u].push_back(i);
        };

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            for (int qIdx : camp[i]) {
                int j = queries[qIdx].v, w = queries[qIdx].w;
                dp[i] = max(dp[i], dp[j - 1] + w);
            };
        };

        cout << dp[n] << '\n';
    };
};  // namespace SUBTASK_23

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    };

    cin >> q;
    queries.reserve(q);
    for (int i = 0; i < q; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        queries.push_back(Query(u, v, w));
    };

    if (q <= 15)
      return SUBTASK_1::Solve(), 0;
    if (SUBTASK_23::checkSubtask())
      return SUBTASK_23::Solve(), 0;
};

컴파일 시 표준 에러 (stderr) 메시지

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40