Submission #710822

#TimeUsernameProblemLanguageResultExecution timeMemory
710822pls33Pipes (BOI13_pipes)C++17
74.07 / 100
163 ms21852 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, 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; } fill[edge] += initial[cur] * 2; 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) { 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; } get_sum(v, sum, count, adj, checked, initial); } } void check_cycle(int v, int64_t prev, int64_t &cur, vvp32 &adj, state_t &checked, vi64 &initial, vi64 &fill) { if (checked[v]) { return; } checked[v] = true; cur = initial[v] - prev; for (auto &[next, edge] : adj[v]) { if (checked[next]) { continue; } check_cycle(next, cur, fill[edge], adj, checked, initial, fill); } } 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; vi64 fill(e); check_leaves(q, checked, 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; } state_t for_check = checked; int64_t sum = 0; int count = 0; int start = (int)distance(degree.begin(), it); get_sum(start, sum, count, adj, checked, initial); sum /= 2; checked = for_check; int id = 0; for (auto &[next, edge] : adj[start]) { if (!checked[next]) { id = edge; break; } } check_cycle(start, sum, fill[id], adj, checked, initial, fill); } for (auto &f : fill) { cout << f << '\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...