제출 #298606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298606		AM1648	통행료 (APIO13_toll)	C++17	0 / 100	1 ms	384 KiB

toll

/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 100010;
const ll maxm = 300010;
const ll maxk = 20;
const ll maxv = maxk * 2;

ll N, M, K, P[maxn], E, cnte[maxn], V, ver[maxv], trans[maxn];
long long Ps[maxn];
pip es1[maxm], es2[maxv];
pii esk[maxk];
vpii tree[maxv];

struct DSU {
    ll par[maxn];
    void init(ll n) {
        iota(par, par + n, 0);
    }
    ll root(ll x) {
        return par[x] == x ? x : par[x] = root(par[x]);
    }
} dsu1, dsu2, dsu3;

void compress_mst() {
    fori (i, K) ++cnte[esk[i].F], ++cnte[esk[i].S];
    sort(es1, es1 + M);
    dsu1.init(N);
    dsu2.init(N); // has more edges
    fori (i, M) {
        auto [a, b] = es1[i].S;
        a = dsu1.root(a), b = dsu2.root(b);
        if (a != b) {
            if (cnte[b] > 0) swap(a, b);
            if (cnte[b] > 0) {
                ll r2a = dsu2.root(a), r2b = dsu2.root(b);
                if (r2a != r2b) {
                    es2[E++] = es1[i];
                    dsu2.par[r2b] = r2a;
                }
            } else {
                dsu1.par[b] = a;
                dsu2.par[b] = a;
                P[a] += P[b];
            }
        }
    }
    fori (i, N) {
        if (dsu1.root(i) == i) {
            trans[i] = V;
            ver[V++] = i;
        }
    }
}

bool dfs2(ll x, ll par, ll trg, ll wt) {
    if (x == trg) return true;
    fori (i, tree[x].size()) {
        ll y = tree[x][i].F;
        if (y != par) {
            if (dfs2(y, x, trg, wt)) {
                if (tree[x][i].S == -1) tree[x][i].S = wt;
                return true;
            }
        }
    }
    return false;
}

bool make_mstk(ll b) {
    dsu3.init(V);
    fori (i, K) {
        if (b >> i & 1) {
            auto [a, b] = esk[i];
            a = trans[a], b = trans[b];
            ll ra = dsu3.root(a), rb = dsu3.root(b);
            if (ra == rb) return false;
            dsu3.par[ra] = rb;
            tree[a].eb(b, -1), tree[b].eb(a, -1);
        }
    }
    fori (i, E) {
        auto [a, b] = es2[i].S;
        a = trans[dsu1.root(a)], b = trans[dsu1.root(b)];
        ll ra = dsu3.root(a), rb = dsu3.root(b);
        if (ra != rb) {
            dsu3.par[ra] = rb;
            tree[a].eb(b, 0), tree[b].eb(a, 0);
        } else {
            dfs2(a, -1, b, es2[i].F);
        }
    }
    return true;
}

long long dfs(ll x, ll par) {
    long long s = 0;
    Ps[x] = P[ver[x]];
    for (auto [y, w] : tree[x]) if (y != par) {
        s += dfs(y, x);
        s += Ps[y] * w;
        Ps[x] += Ps[y];
    }
    return s;
}

long long fix_k() {
    ll rot = trans[dsu1.root(0)];
    long long mx = 0;
    fori (b, 1 << K) {
        fori (i, V) tree[i].clear();
        if (make_mstk(b)) {
            long long v = dfs(rot, -1);
            smax(mx, v);
        }
    }
    return mx;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> N >> M >> K;
    fori (i, M) {
        ll a, b, c; cin >> a >> b >> c; --a, --b;
        es1[i] = {c, {a, b}};
    }
    fori (i, K) {
        ll a, b; cin >> a >> b; --a, --b;
        esk[i] = {a, b};
    }
    fori (i, N) cin >> P[i];

    compress_mst();
    long long ans = fix_k();
    cout << ans << '\n';

}

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

toll.cpp: In function 'bool dfs2(ll, ll, ll, ll)':
toll.cpp:26:44: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define forifrom(i, s, n) for (ll i = s; i < n; ++i)
      |                                            ^
toll.cpp:28:20: note: in expansion of macro 'forifrom'
   28 | #define fori(i, n) forifrom (i, 0, n)
      |                    ^~~~~~~~
toll.cpp:112:5: note: in expansion of macro 'fori'
  112 |     fori (i, tree[x].size()) {
      |     ^~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22