제출 #706881

#제출 시각아이디문제언어결과실행 시간메모리
706881DennisTran통행료 (APIO13_toll)C++17
78 / 100
2540 ms18604 KiB
#pragma GCC optimize("O2") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) for (int i = 0; i < (n); i++) #define ALL(x) (x).begin(), (x).end() #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define ii pair <int, int> #define fi first #define se second #define int long long using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r) { return l + rnd() % (r - l + 1); } const int MAXN = 3e5 + 5; const int MAXK = 25; int N, M, K, c[MAXN], tid[MAXN], tplt = 0, sup[MAXK], h[MAXK], p[MAXK], w[MAXK]; struct Edge{ int u, v, w; friend bool operator < (Edge &A, Edge &B) { return A.w < B.w; } } e[MAXN], q[MAXK]; struct DSU{ int root[MAXN]; int get(int u) {return root[u] == 0 ? u : root[u] = get(root[u]);} bool merge(int u, int v) { if ((u = get(u)) == (v = get(v))) return false; return root[v] = u, true; } } ds[6]; vector <int> Compress_Edges; void Make_Tree(void) { sort(e + 1, e + M + 1); FOR(i, 1, K) ds[2].merge(q[i].u, q[i].v); FOR(i, 1, M) if (ds[1].merge(e[i].u, e[i].v)) { if (ds[2].merge(e[i].u, e[i].v)) ds[3].merge(e[i].u, e[i].v); else Compress_Edges.emplace_back(i); } FOR(i, 1, N) if (ds[3].get(i) == i) tid[i] = ++tplt; FOR(i, 1, N) { sup[tid[ds[3].get(i)]] += c[i]; } FOR(i, 1, M) { e[i].u = tid[ds[3].get(e[i].u)]; e[i].v = tid[ds[3].get(e[i].v)]; } FOR(i, 1, K) { q[i].u = tid[ds[3].get(q[i].u)]; q[i].v = tid[ds[3].get(q[i].v)]; } } vector <int> ke[MAXK]; void DFS(int u) { for (int v : ke[u]) if (v != p[u]) { p[v] = u; h[v] = h[u] + 1; DFS(v); } } int DFS_Calc(int u, int now = 0) { int res = now * sup[u]; for (int v : ke[u]) if (v != p[u]) { res += DFS_Calc(v, now + w[v]); } return res; } void solve(void) { cin >> N >> M >> K; FOR(i, 1, M) cin >> e[i].u >> e[i].v >> e[i].w; FOR(i, 1, K) cin >> q[i].u >> q[i].v; FOR(i, 1, N) cin >> c[i]; Make_Tree(); int ans = 0; REP(mask, 1 << K) { FOR(i, 1, tplt) { ke[i].clear(); } FOR(i, 1, N) ds[4].root[i] = ds[5].root[i] = 0; FOR(i, 1, K) if ((mask >> i - 1) & 1) { if (ds[4].merge(q[i].u, q[i].v)) { ke[q[i].u].emplace_back(q[i].v); ke[q[i].v].emplace_back(q[i].u); } } deque <Edge> MST_Edges; for (int i : Compress_Edges) { if (ds[4].merge(e[i].u, e[i].v)) { ke[e[i].u].emplace_back(e[i].v); ke[e[i].v].emplace_back(e[i].u); MST_Edges.push_front({e[i].u, e[i].v, 0}); } else { MST_Edges.push_back(e[i]); } } DFS(tid[ds[3].get(1)]); for (auto x : MST_Edges) { int u = ds[5].get(x.u), v = ds[5].get(x.v); while (u != v) { if (h[u] < h[v]) swap(u, v); w[u] = x.w; ds[5].merge(p[u], u); u = ds[5].get(u); } } ans = max(ans, DFS_Calc(tid[ds[3].get(1)])); } cout << ans; } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); file("TASK"); //int T; cin >> T; while (T--) solve(); cerr << "Time elapsed: " << TIME << " s.\n"; return (0 ^ 0); }

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

toll.cpp: In function 'void solve()':
toll.cpp:101:37: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  101 |         FOR(i, 1, K) if ((mask >> i - 1) & 1) {
      |                                   ~~^~~
toll.cpp: In function 'int main()':
toll.cpp:9:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:139:5: note: in expansion of macro 'file'
  139 |     file("TASK");
      |     ^~~~
toll.cpp:9:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:139:5: note: in expansion of macro 'file'
  139 |     file("TASK");
      |     ^~~~
#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...