結果

問題 No.3751 Nonopoly
コンテスト
ユーザー marc2825
提出日時 2026-08-08 18:42:59
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,475 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,168 ms
コンパイル使用メモリ 224,864 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2026-10-02 20:53:24
合計ジャッジ時間 8,060 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long w;
};

int N, M;
vector<Edge> edges;

map<pair<int, int>, long long> memo;

long long dfs(int used, int alice) {
    int turn = __builtin_popcount((unsigned)used);

    if (turn == N) {
        int bob = used ^ alice;

        long long score = 0;
        for (auto [u, v, w] : edges) {
            bool au = (alice >> u) & 1;
            bool av = (alice >> v) & 1;
            bool bu = (bob >> u) & 1;
            bool bv = (bob >> v) & 1;

            if (au && av) score += w;
            if (bu && bv) score -= w;
        }

        return score;
    }

    auto key = make_pair(used, alice);
    if (memo.count(key)) return memo[key];

    bool alice_turn = (turn % 2 == 0);

    long long res = alice_turn ? LLONG_MIN : LLONG_MAX;

    for (int v = 0; v < N; ++v) {
        if (used >> v & 1) continue;

        int nused = used | (1 << v);
        int nalice = alice;

        if (alice_turn) {
            nalice |= 1 << v;
        }

        long long val = dfs(nused, nalice);

        if (alice_turn) {
            res = max(res, val);
        } else {
            res = min(res, val);
        }
    }

    return memo[key] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    edges.resize(M);
    for (auto &[u, v, w] : edges) {
        cin >> u >> v >> w;
        --u;
        --v;
    }

    cout << dfs(0, 0) << '\n';
}
0