oj.uz

Submission #261670

# Submission time Handle Problem Language Result Execution time Memory
261670 2020-08-12T00:14:13 Z rama_pang Graph (BOI20_graph) C++14
100 / 100
 614 ms 27500 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  vector<vector<pair<int, int>>> adj(N);
  for (int i = 0; i < M; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    adj[u].emplace_back(v, 2 * c);
    adj[v].emplace_back(u, 2 * c);
  }

  const int UNDET = 1e9;
  vector<int> ans(N, UNDET);
  vector<set<pair<int, int>>> state(N);
  vector<int> trial(N, UNDET);

  for (int i = 0; i < N; i++) {
    if (ans[i] != UNDET) {
      continue;
    }
    static queue<int> q;
    static vector<int> vis;
    q.emplace(i);
    state[i].insert({1, 0}); // ax + b, x = ans[i]
    while (!q.empty()) {
      int u = q.front();
      vis.emplace_back(u);
      q.pop();
      for (auto e : adj[u]) {
        int v = e.first;
        int c = e.second;
        for (auto it : state[u]) {
          if (state[v].count({-it.first, c - it.second}) == 0) {
            state[v].insert({-it.first, c - it.second});
            q.emplace(v);
          }
        }
        if (state[v].size() > 2) {
          cout << "NO\n";
          return 0;
        }
      }
    }

    int x = UNDET;
    for (auto u : vis) {
      if (state[u].size() == 1) {
        continue;
      }
      int a = begin(state[u])->first;
      int b = begin(state[u])->second;
      int c = next(begin(state[u]))->first;
      int d = next(begin(state[u]))->second;
      if (a == c && b != d) {
        cout << "NO\n";
        return 0;
      }
      x = (d - b) / (a - c);
      break;
    }
    
    if (x != UNDET) {
      for (auto u : vis) {
        ans[u] = begin(state[u])->first * x + begin(state[u])->second;
      }
      for (auto u : vis) {
        for (auto e : adj[u]) {
          int v = e.first;
          int c = e.second;
          if (ans[u] + ans[v] != c) {
            cout << "NO\n";
            return 0;
          }
        }
      }
    } else {
      auto FindCost = [&](int st) {
        for (auto u : vis) {
          trial[u] = UNDET;
        }
        trial[i] = st;
        long long cur = 0;
        bool can = true;
        for (auto u : vis) {
          if (!can) {
            break;
          }
          cur += max(trial[u], -trial[u]);
          for (auto e : adj[u]) {
            int v = e.first;
            int c = e.second;
            if (trial[v] == UNDET) {
              trial[v] = c - trial[u];
            }
            if (trial[u] + trial[v] != c) {
              can = false;
              break;
            }
          }
        }
        return can ? cur : UNDET;
      };

      int lo = -1e7, hi = 1e7;
      while (lo < hi) {
        int md = (lo + hi) >> 1;
        if (FindCost(md) < FindCost(md + 1)) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      FindCost(lo);
      for (auto u : vis) {
        ans[u] = trial[u];
      }
    }
    vis.clear();
    if (ans[i] == UNDET) {
      cout << "NO\n";
      return 0;
    }
  }

  cout << "YES\n";
  for (int i = 0; i < N; i++) {
    cout << (double) ans[i] / 2 << " ";
  }
  cout << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB answer = YES
2 Correct 1 ms 384 KB answer = YES
3 Correct 1 ms 384 KB answer = YES
4 Correct 0 ms 384 KB answer = NO
5 Correct 0 ms 384 KB answer = YES
6 Correct 1 ms 384 KB answer = YES
7 Correct 0 ms 384 KB answer = YES
8 Correct 1 ms 384 KB answer = YES
9 Correct 1 ms 384 KB answer = NO
10 Correct 1 ms 384 KB answer = YES
11 Correct 1 ms 384 KB answer = YES
12 Correct 1 ms 384 KB answer = NO
13 Correct 0 ms 384 KB answer = YES
14 Correct 1 ms 384 KB answer = YES
15 Correct 0 ms 384 KB answer = YES
16 Correct 0 ms 384 KB answer = YES
17 Correct 1 ms 384 KB answer = YES
18 Correct 0 ms 384 KB answer = YES
19 Correct 1 ms 384 KB answer = YES
20 Correct 1 ms 384 KB answer = YES
21 Correct 0 ms 384 KB answer = YES
22 Correct 0 ms 384 KB answer = NO
23 Correct 1 ms 384 KB answer = NO
24 Correct 1 ms 384 KB answer = YES
25 Correct 1 ms 384 KB answer = YES
26 Correct 1 ms 384 KB answer = YES
27 Correct 1 ms 384 KB answer = YES
28 Correct 1 ms 384 KB answer = YES
29 Correct 1 ms 384 KB answer = YES
30 Correct 0 ms 384 KB answer = NO
31 Correct 1 ms 384 KB answer = YES
32 Correct 1 ms 384 KB answer = YES
33 Correct 1 ms 384 KB answer = YES
34 Correct 1 ms 384 KB answer = YES
35 Correct 1 ms 384 KB answer = YES
36 Correct 1 ms 384 KB answer = YES
37 Correct 1 ms 384 KB answer = YES
38 Correct 1 ms 384 KB answer = YES
39 Correct 1 ms 384 KB answer = YES
40 Correct 2 ms 512 KB answer = YES
41 Correct 1 ms 512 KB answer = NO
42 Correct 2 ms 512 KB answer = YES
43 Correct 2 ms 512 KB answer = YES
44 Correct 2 ms 512 KB answer = YES
45 Correct 3 ms 512 KB answer = YES
46 Correct 1 ms 384 KB answer = YES
47 Correct 2 ms 640 KB answer = YES
48 Correct 2 ms 640 KB answer = YES
49 Correct 23 ms 2208 KB answer = YES
50 Correct 14 ms 2688 KB answer = YES
51 Correct 21 ms 2176 KB answer = YES
52 Correct 5 ms 1664 KB answer = NO
53 Correct 2 ms 512 KB answer = YES
54 Correct 5 ms 768 KB answer = YES
55 Correct 11 ms 1312 KB answer = YES
56 Correct 23 ms 2168 KB answer = YES
57 Correct 20 ms 2176 KB answer = YES
58 Correct 19 ms 1920 KB answer = YES
59 Correct 12 ms 2432 KB answer = YES
60 Correct 23 ms 2176 KB answer = YES
61 Correct 7 ms 1536 KB answer = YES
62 Correct 75 ms 7948 KB answer = NO
63 Correct 125 ms 8440 KB answer = YES
64 Correct 131 ms 8440 KB answer = NO
65 Correct 132 ms 8568 KB answer = YES
66 Correct 4 ms 768 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB answer = YES
2 Correct 1 ms 384 KB answer = YES
3 Correct 1 ms 384 KB answer = YES
4 Correct 0 ms 384 KB answer = NO
5 Correct 0 ms 384 KB answer = YES
6 Correct 1 ms 384 KB answer = YES
7 Correct 0 ms 384 KB answer = YES
8 Correct 1 ms 384 KB answer = YES
9 Correct 1 ms 384 KB answer = NO
10 Correct 1 ms 384 KB answer = YES
11 Correct 1 ms 384 KB answer = YES
12 Correct 1 ms 384 KB answer = NO
13 Correct 0 ms 384 KB answer = YES
14 Correct 1 ms 384 KB answer = YES
15 Correct 0 ms 384 KB answer = YES
16 Correct 0 ms 384 KB answer = YES
17 Correct 1 ms 384 KB answer = YES
18 Correct 0 ms 384 KB answer = YES
19 Correct 1 ms 384 KB answer = YES
20 Correct 1 ms 384 KB answer = YES
21 Correct 0 ms 384 KB answer = YES
22 Correct 0 ms 384 KB answer = NO
23 Correct 1 ms 384 KB answer = NO
24 Correct 1 ms 384 KB answer = YES
25 Correct 1 ms 384 KB answer = YES
26 Correct 1 ms 384 KB answer = YES
27 Correct 1 ms 384 KB answer = YES
28 Correct 1 ms 384 KB answer = YES
29 Correct 1 ms 384 KB answer = YES
30 Correct 0 ms 384 KB answer = NO
31 Correct 1 ms 384 KB answer = YES
32 Correct 1 ms 384 KB answer = YES
33 Correct 1 ms 384 KB answer = YES
34 Correct 1 ms 384 KB answer = YES
35 Correct 1 ms 384 KB answer = YES
36 Correct 1 ms 384 KB answer = YES
37 Correct 1 ms 384 KB answer = YES
38 Correct 1 ms 384 KB answer = YES
39 Correct 1 ms 384 KB answer = YES
40 Correct 2 ms 512 KB answer = YES
41 Correct 1 ms 512 KB answer = NO
42 Correct 2 ms 512 KB answer = YES
43 Correct 2 ms 512 KB answer = YES
44 Correct 2 ms 512 KB answer = YES
45 Correct 3 ms 512 KB answer = YES
46 Correct 1 ms 384 KB answer = YES
47 Correct 2 ms 640 KB answer = YES
48 Correct 2 ms 640 KB answer = YES
49 Correct 23 ms 2208 KB answer = YES
50 Correct 14 ms 2688 KB answer = YES
51 Correct 21 ms 2176 KB answer = YES
52 Correct 5 ms 1664 KB answer = NO
53 Correct 2 ms 512 KB answer = YES
54 Correct 5 ms 768 KB answer = YES
55 Correct 11 ms 1312 KB answer = YES
56 Correct 23 ms 2168 KB answer = YES
57 Correct 20 ms 2176 KB answer = YES
58 Correct 19 ms 1920 KB answer = YES
59 Correct 12 ms 2432 KB answer = YES
60 Correct 23 ms 2176 KB answer = YES
61 Correct 7 ms 1536 KB answer = YES
62 Correct 75 ms 7948 KB answer = NO
63 Correct 125 ms 8440 KB answer = YES
64 Correct 131 ms 8440 KB answer = NO
65 Correct 132 ms 8568 KB answer = YES
66 Correct 4 ms 768 KB answer = YES
67 Correct 178 ms 18032 KB answer = YES
68 Correct 193 ms 18032 KB answer = YES
69 Correct 122 ms 23020 KB answer = YES
70 Correct 188 ms 27500 KB answer = YES
71 Correct 127 ms 23276 KB answer = YES
72 Correct 588 ms 18672 KB answer = YES
73 Correct 224 ms 23660 KB answer = YES
74 Correct 111 ms 15344 KB answer = YES
75 Correct 41 ms 10232 KB answer = NO
76 Correct 29 ms 2560 KB answer = YES
77 Correct 65 ms 4836 KB answer = YES
78 Correct 122 ms 8180 KB answer = YES
79 Correct 398 ms 15984 KB answer = YES
80 Correct 167 ms 11892 KB answer = YES
81 Correct 80 ms 14836 KB answer = NO
82 Correct 208 ms 23404 KB answer = YES
83 Correct 228 ms 23276 KB answer = YES
84 Correct 614 ms 18160 KB answer = YES
85 Correct 168 ms 18032 KB answer = YES
86 Correct 127 ms 23148 KB answer = YES
87 Correct 96 ms 16756 KB answer = NO
88 Correct 240 ms 22512 KB answer = YES
89 Correct 166 ms 22392 KB answer = YES
90 Correct 169 ms 22396 KB answer = YES
91 Correct 184 ms 22424 KB answer = YES
92 Correct 98 ms 12144 KB answer = YES
93 Correct 91 ms 12016 KB answer = YES
94 Correct 177 ms 23020 KB answer = NO
95 Correct 69 ms 13944 KB answer = NO
96 Correct 423 ms 27372 KB answer = YES
97 Correct 74 ms 22892 KB answer = NO