제출 #1266986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266986		ducdev	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	1095 ms	14216 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) {};
};

int n, q, timer, lg;
int tin[MAX_N + 5], tout[MAX_N + 5], up[MAX_N + 5][18], depth[MAX_N + 5];
int dp[MAX_N + 5], dpWithoutNode[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;

    int par[N + 5], depth[N + 5];
    int version[N + 5];

    void dfs(int u, int p) {
        par[u] = p;
        depth[u] = depth[p] + 1;
        for (int v : adj[u])
            if (v != p) dfs(v, u);
    };

    vector<int> tracePath(int u, int v) {
        vector<int> pathU, pathV;
        if (depth[u] > depth[v]) swap(u, v);

        while (depth[v] > depth[u]) {
            pathV.push_back(v);
            v = par[v];
        };

        while (u != v) {
            pathU.push_back(u);
            pathV.push_back(v);
            u = par[u], v = par[v];
        };
        pathU.push_back(u);
        for (int i = (int)pathV.size() - 1; i >= 0; i--) pathU.push_back(pathV[i]);

        return pathU;
    };

    void Solve() {
        dfs(1, 1);

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

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

                    for (int u : path) {
                        if (version[u] == mask) {
                            valid = false;
                            break;
                        };
                        version[u] = mask;
                    };
                    if (!valid) break;
                };
                if (!valid) break;
            };

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

        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:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         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