Submission #710806

#TimeUsernameProblemLanguageResultExecution timeMemory
710806pls33Pipes (BOI13_pipes)C++17
74.07 / 100
177 ms22088 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, bool mult) { 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] * (1 + int(mult)); initial[next] -= initial[cur]; degree[next]--; if (degree[next] == 1) { q.push(next); } } degree[cur] = max(0, degree[cur] - 1); } } int main() { #ifndef _AAAAAAAAA ios_base::sync_with_stdio(false); cin.tie(0); #else freopen("pipes.in", "r", stdin); freopen("pipes.out", "w", stdout); #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, true); 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) { q.push((int)distance(degree.begin(), it)); check_leaves(q, checked, fill, initial, degree, adj, false); } 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...