oj.uz

Submission #1024719

# Submission time Handle Problem Language Result Execution time Memory
1024719 2024-07-16T09:40:55 Z NeroZein Graph (BOI20_graph) C++17
100 / 100
 238 ms 36200 KB 
#include "bits/stdc++.h"
using namespace std;
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#pragma GCC target("avx2,fma")

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5;
const long long INF = 1e15;

bool vis[N];
bool vis2[N];
bool color[N];
stack<int> stk;
long long val[N];
vector<int> component;
vector<int> odd_cycle;
vector<pair<int, int>> g[N];

bool check_not_bipartite(int v, int c) {
  if (vis[v]) {
    if (color[v] != c && odd_cycle.empty()) {
      odd_cycle.push_back(v);
      while (true) {
        int x = stk.top();
        stk.pop();
        odd_cycle.push_back(x); 
        if (x == v) {
          break; 
        }
      }
      return true;
    }
    return false; 
  }
  vis[v] = true; 
  stk.push(v);
  color[v] = c; 
  component.push_back(v); 
  bool ret = false; 
  for (auto [u, w] : g[v]) {
    ret |= check_not_bipartite(u, c ^ 1); 
  }
  if (!stk.empty() && stk.top() == v) {
    stk.pop();    
  }
  return ret; 
}

long long assign(int v, long long c) {
  if (c > INF) {
    return INF;
  }
  if (vis2[v]) {
    if (val[v] != c) {
      return INF;
    }
    return 0;
  }
  vis2[v] = true;
  val[v] = c;
  long long ret = abs(c); 
  for (auto [u, w] : g[v]) {
    ret += assign(u, w - c);
    ret = min(ret, INF);
  }
  return ret; 
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  map<pair<int, int>, int> mp;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    w *= 2;
    if (u > v) swap(u, v);
    if (!mp.count({u, v})) {
      mp[{u, v}] = w;
      g[u].push_back({v, w});
      g[v].push_back({u, w});
    }
    if (mp[{u, v}] != w) {
      cout << "NO" << '\n';
      return 0; 
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) {
      continue; 
    }
    while (!stk.empty()) stk.pop();
    bool not_bipartite = check_not_bipartite(i, 0); 
    if (not_bipartite) {
      int sum = 0;
      for (int j = 1; j < (int) odd_cycle.size(); ++j) {
        int u = odd_cycle[j - 1], v = odd_cycle[j];
        if (u > v) swap(u, v);
        sum += mp[{u, v}] * (j % 2 ? 1 : -1);
      }
      int rt = odd_cycle[0];
      long long x = assign(rt, sum / 2);
      if (x == INF) {
        cout << "NO" << '\n';
        return 0; 
      }
      odd_cycle.clear();
    } else {
      long long x = assign(i, 0);
      if (x == INF) {
        cout << "NO" << '\n';
        return 0; 
      }
      vector<long long> offset;
      for (int v : component) {
        //debug(v, val[v]); 
        offset.push_back(val[v] * (color[v] == 1 ? 1 : -1));
      }
      sort(offset.begin(), offset.end());
      //debug(offset);
      for (int v : component) {
        vis2[v] = 0; 
      }
      x = offset[offset.size() / 2];
      assign(i, x); 
    }
    component.clear();
  }
  for (auto [e, w] : mp) {
    if (val[e.first] + val[e.second] != w) {
      cout << "NO" << '\n';
      return 0; 
    }
  }
  cout << "YES" << '\n';
  for (int i = 1; i <= n; ++i) {
    cout << (val[i] / 2.0) << ' ';
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB answer = YES
2 Correct 1 ms 2652 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 1 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2652 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2652 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB answer = YES
2 Correct 1 ms 2652 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 1 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2652 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2652 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2648 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2652 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 1 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB answer = YES
2 Correct 1 ms 2652 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 1 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2652 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2652 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2648 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2652 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 1 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES
37 Correct 1 ms 2652 KB answer = YES
38 Correct 1 ms 2720 KB answer = YES
39 Correct 1 ms 2908 KB answer = YES
40 Correct 1 ms 2960 KB answer = YES
41 Correct 1 ms 2908 KB answer = NO
42 Correct 1 ms 2908 KB answer = YES
43 Correct 1 ms 2908 KB answer = YES
44 Correct 1 ms 2908 KB answer = YES
45 Correct 2 ms 2904 KB answer = YES
46 Correct 1 ms 2652 KB answer = YES
47 Correct 1 ms 2908 KB answer = YES
48 Correct 2 ms 2908 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB answer = YES
2 Correct 1 ms 2652 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 1 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2652 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2652 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2648 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2652 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 1 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES
37 Correct 1 ms 2652 KB answer = YES
38 Correct 1 ms 2720 KB answer = YES
39 Correct 1 ms 2908 KB answer = YES
40 Correct 1 ms 2960 KB answer = YES
41 Correct 1 ms 2908 KB answer = NO
42 Correct 1 ms 2908 KB answer = YES
43 Correct 1 ms 2908 KB answer = YES
44 Correct 1 ms 2908 KB answer = YES
45 Correct 2 ms 2904 KB answer = YES
46 Correct 1 ms 2652 KB answer = YES
47 Correct 1 ms 2908 KB answer = YES
48 Correct 2 ms 2908 KB answer = YES
49 Correct 11 ms 4172 KB answer = YES
50 Correct 10 ms 4440 KB answer = YES
51 Correct 11 ms 4696 KB answer = YES
52 Correct 7 ms 4444 KB answer = NO
53 Correct 2 ms 2908 KB answer = YES
54 Correct 3 ms 3160 KB answer = YES
55 Correct 5 ms 3420 KB answer = YES
56 Correct 10 ms 4108 KB answer = YES
57 Correct 10 ms 3928 KB answer = YES
58 Correct 9 ms 3784 KB answer = YES
59 Correct 9 ms 3672 KB answer = YES
60 Correct 11 ms 3932 KB answer = YES
61 Correct 5 ms 3420 KB answer = YES
62 Correct 8 ms 3932 KB answer = NO
63 Correct 163 ms 20560 KB answer = YES
64 Correct 171 ms 20684 KB answer = NO
65 Correct 161 ms 20564 KB answer = YES
66 Correct 2 ms 2904 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB answer = YES
2 Correct 1 ms 2652 KB answer = YES
3 Correct 1 ms 2652 KB answer = YES
4 Correct 1 ms 2652 KB answer = NO
5 Correct 1 ms 2652 KB answer = YES
6 Correct 1 ms 2652 KB answer = YES
7 Correct 1 ms 2652 KB answer = YES
8 Correct 1 ms 2652 KB answer = YES
9 Correct 1 ms 2652 KB answer = NO
10 Correct 1 ms 2652 KB answer = YES
11 Correct 1 ms 2652 KB answer = YES
12 Correct 1 ms 2652 KB answer = NO
13 Correct 1 ms 2652 KB answer = YES
14 Correct 1 ms 2652 KB answer = YES
15 Correct 1 ms 2652 KB answer = YES
16 Correct 1 ms 2652 KB answer = YES
17 Correct 1 ms 2652 KB answer = YES
18 Correct 1 ms 2652 KB answer = YES
19 Correct 1 ms 2652 KB answer = YES
20 Correct 1 ms 2652 KB answer = YES
21 Correct 1 ms 2652 KB answer = YES
22 Correct 1 ms 2652 KB answer = NO
23 Correct 1 ms 2652 KB answer = NO
24 Correct 1 ms 2652 KB answer = YES
25 Correct 1 ms 2652 KB answer = YES
26 Correct 1 ms 2652 KB answer = YES
27 Correct 1 ms 2652 KB answer = YES
28 Correct 1 ms 2652 KB answer = YES
29 Correct 1 ms 2648 KB answer = YES
30 Correct 1 ms 2652 KB answer = NO
31 Correct 1 ms 2652 KB answer = YES
32 Correct 1 ms 2652 KB answer = YES
33 Correct 1 ms 2652 KB answer = YES
34 Correct 1 ms 2652 KB answer = YES
35 Correct 1 ms 2652 KB answer = YES
36 Correct 1 ms 2652 KB answer = YES
37 Correct 1 ms 2652 KB answer = YES
38 Correct 1 ms 2720 KB answer = YES
39 Correct 1 ms 2908 KB answer = YES
40 Correct 1 ms 2960 KB answer = YES
41 Correct 1 ms 2908 KB answer = NO
42 Correct 1 ms 2908 KB answer = YES
43 Correct 1 ms 2908 KB answer = YES
44 Correct 1 ms 2908 KB answer = YES
45 Correct 2 ms 2904 KB answer = YES
46 Correct 1 ms 2652 KB answer = YES
47 Correct 1 ms 2908 KB answer = YES
48 Correct 2 ms 2908 KB answer = YES
49 Correct 11 ms 4172 KB answer = YES
50 Correct 10 ms 4440 KB answer = YES
51 Correct 11 ms 4696 KB answer = YES
52 Correct 7 ms 4444 KB answer = NO
53 Correct 2 ms 2908 KB answer = YES
54 Correct 3 ms 3160 KB answer = YES
55 Correct 5 ms 3420 KB answer = YES
56 Correct 10 ms 4108 KB answer = YES
57 Correct 10 ms 3928 KB answer = YES
58 Correct 9 ms 3784 KB answer = YES
59 Correct 9 ms 3672 KB answer = YES
60 Correct 11 ms 3932 KB answer = YES
61 Correct 5 ms 3420 KB answer = YES
62 Correct 8 ms 3932 KB answer = NO
63 Correct 163 ms 20560 KB answer = YES
64 Correct 171 ms 20684 KB answer = NO
65 Correct 161 ms 20564 KB answer = YES
66 Correct 2 ms 2904 KB answer = YES
67 Correct 87 ms 24524 KB answer = YES
68 Correct 92 ms 24680 KB answer = YES
69 Correct 88 ms 24148 KB answer = YES
70 Correct 141 ms 36200 KB answer = YES
71 Correct 90 ms 24272 KB answer = YES
72 Correct 118 ms 15184 KB answer = YES
73 Correct 105 ms 14544 KB answer = YES
74 Correct 69 ms 15076 KB answer = YES
75 Correct 60 ms 14796 KB answer = NO
76 Correct 12 ms 4372 KB answer = YES
77 Correct 25 ms 5980 KB answer = YES
78 Correct 44 ms 8276 KB answer = YES
79 Correct 95 ms 13648 KB answer = YES
80 Correct 75 ms 15248 KB answer = YES
81 Correct 113 ms 18892 KB answer = NO
82 Correct 127 ms 23112 KB answer = YES
83 Correct 148 ms 24256 KB answer = YES
84 Correct 120 ms 24520 KB answer = YES
85 Correct 87 ms 24520 KB answer = YES
86 Correct 92 ms 24136 KB answer = YES
87 Correct 86 ms 16208 KB answer = NO
88 Correct 142 ms 18192 KB answer = YES
89 Correct 115 ms 13392 KB answer = YES
90 Correct 128 ms 13392 KB answer = YES
91 Correct 101 ms 13396 KB answer = YES
92 Correct 61 ms 8660 KB answer = YES
93 Correct 50 ms 8656 KB answer = YES
94 Correct 85 ms 23244 KB answer = NO
95 Correct 56 ms 13248 KB answer = NO
96 Correct 238 ms 29244 KB answer = YES
97 Correct 57 ms 23240 KB answer = NO