Submission #710825

#TimeUsernameProblemLanguageResultExecution timeMemory
710825pls33Pipes (BOI13_pipes)C++17
67.59 / 100
160 ms43692 KiB
// boi2013 d1p3 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #pragma region dalykai using p32 = pair<int, int>; using p32u = pair<uint32_t, uint32_t>; using p64 = pair<int64_t, int64_t>; using p64u = pair<uint64_t, uint64_t>; using vi16 = vector<int16_t>; using vi16u = vector<uint16_t>; using vi32 = vector<int>; using vi32u = vector<uint32_t>; using vi64 = vector<int64_t>; using vi64u = vector<uint64_t>; using vp32 = vector<p32>; using vp32u = vector<p32u>; using vp64 = vector<p64>; using vp64u = vector<p64u>; using vvi32 = vector<vi32>; using vvi32u = vector<vi32u>; using vvi64 = vector<vi64>; using vvi64u = vector<vi64u>; using vvp32 = vector<vp32>; using vvp32u = vector<vp32u>; using vvp64 = vector<vp64>; using vvp64u = vector<vp64u>; using f80 = long double; #pragma endregion using state_t = bitset<(int)1e5>; void check_leaves(queue<int> &q, state_t &checked, state_t &edged, vi64 &fill, vi64 &initial, vi32 &degree, vvp32 &adj) { while (!q.empty()) { int cur = q.front(); checked[cur] = true; q.pop(); for (auto &[next, edge] : adj[cur]) { if (checked[next]) { continue; } edged[edge] = true; fill[edge] += initial[cur]; initial[next] -= initial[cur]; degree[next]--; if (degree[next] == 1) { q.push(next); } } degree[cur] = max(0, degree[cur] - 1); } } void get_sum(int v, int64_t &sum, int &count, vvp32 &adj, state_t &checked, vi64 &initial, vp32 &thing) { if (checked[v]) { return; } sum += (count % 2) ? -initial[v] : initial[v]; count++; checked[v] = true; for (auto &[next, edge] : adj[v]) { if (checked[next]) { continue; } thing.emplace_back(v, edge); get_sum(v, sum, count, adj, checked, initial, thing); } } int main() { #ifndef _AAAAAAAAA ios_base::sync_with_stdio(false); cin.tie(0); #else freopen("pipes.in", "r", stdin); #ifndef __linux__ atexit([]() { freopen("con", "r", stdin); system("pause"); }); #endif #endif int v, e; cin >> v >> e; vi64 initial(v); for (auto &i : initial) { cin >> i; } vvp32 adj(v); vi32 degree(v); for (int i = 0; i < e; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].emplace_back(b, i); adj[b].emplace_back(a, i); degree[a]++; degree[b]++; } // kadangi jungus grafas, pirma atmetam visas medzio dalis ir po to jei lieka // nelyginis ciklas (is 2k+1 virsuniu), tai sutvarkom ji // jei lieka kazkoks keistas darinys, tai isvedam 0 queue<int> q; for (int i = 0; i < v; i++) { if (degree[i] == 1) { q.push(i); } } state_t checked, edged; vi64 fill(e); check_leaves(q, checked, edged, fill, initial, degree, adj); auto it = max_element(degree.begin(), degree.end()); if (*it > 2 || (v - checked.count() && !((v - checked.count()) % 2))) { cout << "0\n"; return 0; } if (*it == 2) { checked.reset(); for (int i = 0; i < v; i++) { checked[i] = degree[i] < 2; } int64_t sum = 0; int count = 0; int start = (int)distance(degree.begin(), it); vp32 thing; get_sum(start, sum, count, adj, checked, initial, thing); sum /= 2; int64_t prev = sum; for (auto &[vertex, edge] : thing) { fill[edge] = initial[vertex] - prev; prev = fill[edge]; edged[edge] = true; } for (int i = 0; i < e; i++) { if (!edged[i]) { fill[i] = sum; break; } } } for (auto &f : fill) { cout << f * 2 << '\n'; } return 0; }

Compilation message (stderr)

pipes.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
pipes.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   33 | #pragma endregion
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...