제출 #298606

#제출 시각아이디문제언어결과실행 시간메모리
298606AM1648통행료 (APIO13_toll)C++17
0 / 100
1 ms384 KiB
/* 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()) {
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...