Guest User

Untitled

a guest
Dec 19th, 2017
527
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <iomanip>
  17. #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22.  
  23. mt19937 rnd(228);
  24.  
  25. const int N = 1e5 + 7;
  26.  
  27. vector <pair <int, int> > g[N];
  28.  
  29. ll c[N];
  30. ll cur[N];
  31. ll ans[N];
  32. bool u[N];
  33. int col[N];
  34. int par[N];
  35. int d[N];
  36. int par_ind[N];
  37.  
  38. int s = -1, t = -1;
  39. int edge_ind = -1;
  40.  
  41. void dfs(int v)
  42. {
  43.     u[v] = true;
  44.     for (auto x : g[v])
  45.     {
  46.         int to = x.first, ind = x.second;
  47.         if (!u[to])
  48.         {
  49.             d[to] = d[v] + 1;
  50.             col[to] = (col[v] ^ 1);
  51.             par[to] = v;
  52.             par_ind[to] = ind;
  53.             dfs(to);
  54.             ans[ind] = cur[to];
  55.             cur[v] -= cur[to];
  56.         }
  57.         else if (d[to] < d[v])
  58.         {
  59.             if (col[to] == col[v])
  60.             {
  61.                 s = v, t = to;
  62.                 edge_ind = ind;
  63.             }
  64.         }
  65.     }
  66. }
  67.  
  68. void solve_tree(int v)
  69. {
  70.     u[v] = true;
  71.     for (auto x : g[v])
  72.     {
  73.         int to = x.first, ind = x.second;
  74.         if (ind != edge_ind && !u[to])
  75.         {
  76.             solve_tree(to);
  77.             ans[ind] = c[to];
  78.             c[v] -= c[to];
  79.         }
  80.     }
  81. }
  82.  
  83.  
  84. int main()
  85. {
  86. #ifdef ONPC
  87.     freopen("a.in", "r", stdin);
  88. #endif
  89.     int n, m;
  90.     scanf("%d%d", &n, &m);
  91.     for (int i = 0; i < n; i++)
  92.     {
  93.         scanf("%lld", &c[i]);
  94.         cur[i] = c[i];
  95.     }
  96.     for (int i = 0; i < m; i++)
  97.     {
  98.         int a, b;
  99.         scanf("%d%d", &a, &b);
  100.         a--, b--;
  101.         g[a].push_back({b, i});
  102.         g[b].push_back({a, i});
  103.     }
  104.     dfs(0);
  105.     if (cur[0] == 0)
  106.     {
  107.         puts("YES");
  108.         for (int i = 0; i < m; i++)
  109.         {
  110.             printf("%lld\n", ans[i]);
  111.         }
  112.         return 0;
  113.     }
  114.     if (edge_ind != -1)
  115.     {
  116.         for (int i = 0; i < m; i++)
  117.         {
  118.             ans[i] = 0;
  119.         }
  120.         for (int i = 0; i < n; i++)
  121.         {
  122.             u[i] = 0;
  123.         }
  124.         solve_tree(s);
  125.         ll get = c[s] / 2;
  126.         int cur = s;
  127.         int sign = 1;
  128.         while (cur != t)
  129.         {
  130.             ans[par_ind[cur]] += sign * get;
  131.             sign *= -1;
  132.             cur = par[cur];
  133.         }
  134.         ans[edge_ind] += sign * get;
  135.         puts("YES");
  136.         for (int i = 0; i < m; i++)
  137.         {
  138.             printf("%lld\n", ans[i]);
  139.         }
  140.     }
  141.     else
  142.     {
  143.         puts("NO");
  144.         return 0;
  145.     }
  146. }
RAW Paste Data