제출 #255588

#제출 시각아이디문제언어결과실행 시간메모리
255588amoo_safarPipes (BOI13_pipes)C++17
100 / 100
329 ms36032 KiB
// Zende bad Shoma nasime faghat ! #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef long long ll; typedef long double ld; typedef string str; typedef pair<ll, ll> pll; const ll Mod = 1000000007LL; const int N = 2e5 + 10; const ll Inf = 2242545357980376863LL; const ll Log = 30; ll n, m, c[N], ans[N]; vector<pll> G[N]; int mk[N]; void Solve(int u){ mk[u] = 1; for(auto [adj, id] : G[u]){ if(!mk[adj]){ Solve(adj); ans[id] = 2 * c[adj]; c[u] -= c[adj]; } } } ll dep[N]; vector<int> vis, C; void Find(int u, int p, int d){ mk[u] = 1; dep[u] = d; vis.pb(u); for(auto [adj, id] : G[u]){ if(adj == p) continue; if(mk[adj]){ for(int i = dep[adj]; i <= dep[u]; i++) C.pb(vis[i]); } else Find(adj, u, d + 1); } vis.pop_back(); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; if(m > n) return cout << "0\n", 0; for(int i = 1; i <= n; i++) cin >> c[i]; ll u, v; map<pll, int> mp; for(int i = 1; i <= m; i++){ cin >> u >> v; G[u].pb({v, i}); G[v].pb({u, i}); mp[{u, v}] = i; mp[{v, u}] = i; } if(m == n - 1){ Solve(1); } else { Find(1, 0, 0); if(C.size() % 2 == 0) return cout << "0\n", 0; memset(mk, 0, sizeof mk); for(auto x : C) mk[x] = 1; for(auto x : C) Solve(x); ll a = 1, b = 0; for(auto x : C){ b = c[x] - b; a = -a; } if(b % 2 != 0) assert(false); ll X = b / 2; ans[mp[ {C[0], C.back() } ]] = 2 * X; a = 1, b = 0; for(int i = 0; i + 1 < C.size(); i++){ ll x = C[i]; b = c[x] - b; a = -a; ans[ mp[{C[i], C[i + 1]}] ] = 2 * (a * X + b); } } for(int i = 1; i <= m; i++) cout << ans[i] << '\n'; return 0; } /* 4 4 2 6 10 0 1 2 2 3 3 1 4 2 */

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

pipes.cpp: In function 'void Find(int, int, int)':
pipes.cpp:45:19: warning: unused variable 'id' [-Wunused-variable]
  for(auto [adj, id] : G[u]){
                   ^
pipes.cpp: In function 'int main()':
pipes.cpp:87:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i + 1 < C.size(); i++){
                  ~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...