제출 #158021

#제출 시각아이디문제언어결과실행 시간메모리
158021DrSwadPipes (BOI13_pipes)C++14
100 / 100
645 ms63176 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #endif typedef long long ll; typedef pair<int, int> pii; #define x first #define y second const int N = 1e5 + 5; int n, m; vector<int> c; vector<set<int>> adj; vector<pii> e; vector<ll> ans; int adjacentNode(int node, int i) { assert(i == 0 || i == 1); int adj_edge = (i == 0 ? *adj[node].begin() : *adj[node].rbegin()); int adj_node = e[adj_edge].x ^ e[adj_edge].y ^ node; return adj_node; } void dfs(int at, int p, int root, vector<pii> &order) { int nxt; nxt = adjacentNode(at, 0); if (nxt != p) order.push_back({at, *adj[at].begin()}); else { nxt = adjacentNode(at, 1); if (nxt != p) order.push_back({at, *adj[at].rbegin()}); } if (nxt != root) dfs(nxt, at, root, order); } int main() { #ifdef LOCAL freopen("in", "r", stdin); freopen("out", "w", stdout); #endif scanf("%d %d", &n, &m); c.resize(n); for (int i = 0; i < n; i++) scanf("%d", &c[i]); adj.resize(n); e.resize(m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); u--, v--; adj[u].insert(i); adj[v].insert(i); e[i] = {u, v}; } ans.resize(m); queue<int> q; for (int i = 0; i < n; i++) q.push(i); while (!q.empty()) { int curr_node = q.front(); q.pop(); if (adj[curr_node].size() == 1) { int adj_edge = *adj[curr_node].begin(); int adj_node = adjacentNode(curr_node, 0); ans[adj_edge] = 2LL * c[curr_node]; c[curr_node] -= ans[adj_edge] / 2; c[adj_node] -= ans[adj_edge] / 2; adj[curr_node].erase(adj_edge); adj[adj_node].erase(adj_edge); if (adj[adj_node].size() == 1) q.push(adj_node); } } int cnt_node = 0; for (int i = 0; i < n; i++) { if (adj[i].size() > 2) { printf("0\n"); return 0; } cnt_node += adj[i].size() == 2; } if (cnt_node > 0 && cnt_node % 2 == 0) { printf("0\n"); return 0; } int first_node; for (first_node = 0; first_node < n; first_node++) { if (adj[first_node].size() == 2) break; } if (first_node < n) { vector<pii> order; dfs(first_node, -1, first_node, order); ll sum = 2LL * c[first_node]; ll diff = 0; for (int i = 1; i < order.size(); i++) { diff = 2LL * c[order[i].x] - diff; } ans[order[0].y] = (sum - diff) / 2LL; for (int i = 1; i < order.size(); i++) { ans[order[i].y] = 2LL * c[order[i].x] - ans[order[i - 1].y]; } } for (int i = 0; i < m; i++) printf("%lld\n", ans[i]); return 0; }

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

pipes.cpp: In function 'int main()':
pipes.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < order.size(); i++) {
                   ~~^~~~~~~~~~~~~~
pipes.cpp:117:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < order.size(); i++) {
                   ~~^~~~~~~~~~~~~~
pipes.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:52:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; i++) scanf("%d", &c[i]);
                              ~~~~~^~~~~~~~~~~~~
pipes.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...