oj.uz

Submission #726746

# Submission time Handle Problem Language Result Execution time Memory
726746 2023-04-19T10:02:34 Z YENGOYAN Graph (BOI20_graph) C++17
58 / 100
 700 ms 17572 KB 
/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e9;

vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };

void solve() {
  int n, m; cin >> n >> m;
  vector<vector<pair<int, int>>> gp(n);
  for(int i = 0; i < m; ++i){
    int u, v, w; cin >> u >> v >> w; w *= 2;
    gp[--u].push_back({--v, w});
    gp[v].push_back({u, w});
  }
  vector<int> ans(n, inf), val(n), comp;
  vector<bool> vis;
  int sm = 0;
  function<void(int)> dfs = [&](int u){
    vis[u] = 1;
    if(sm != inf) {
      sm += abs(val[u]);
    }
    for(pair<int, int> &v : gp[u]) {
      if(!vis[v.first]) {
        val[v.first] = v.second - val[u];
        dfs(v.first); 
      }
      else if(val[u] + val[v.first] != v.second) {
        sm = inf;
      }
    }
  };
  vector<int> res(n, 1e9);
  vector<int> start(n, -1e9);
  for(int a = -60; a <= 60; ++a){
    vis = vector<bool> (n);
    val = vector<int> (n);
    for(int i = 0; i < n; ++i) {
      if(vis[i]) {
        continue;
      }
      sm = 0;
      val[i] = a;
      dfs(i);
      if(start[i] == -1e9) {
        start[i] = a;
      }
      if(sm < ans[i]) {
        start[i] = a;
        ans[i] = sm;
      }
    }
  }
  bool f = 0;
  function<void(int)> res_dfs = [&](int u){
    if(f) {
      return;
    }
    res[u] = val[u];
    vis[u] = 1;
    for(pair<int, int> &v : gp[u]){
      if(!vis[v.first]) {
        val[v.first] = v.second - val[u];
        res_dfs(v.first);
      }
      else if(val[u] + val[v.first] != v.second) {
        f = 1;
        return;
      }
    }
  
  };

  vis = vector<bool> (n);
  val = vector<int> (n);
  for(int i = 0; i < n; ++i){
    if(vis[i]) {
      continue;
    }
    val[i] = start[i];
    res_dfs(i); 
    if(f) {
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
  for(int i = 0; i < n; ++i) {
    cout << res[i] / 2.0 << " ";
  }
  cout << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 // int t; cin >> t; while(t--)
    solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 316 KB answer = YES
6 Correct 0 ms 320 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 328 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 320 KB answer = YES
16 Correct 0 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 1 ms 316 KB answer = YES
19 Correct 1 ms 316 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 1 ms 316 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 1 ms 212 KB answer = YES
25 Correct 1 ms 320 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 212 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 1 ms 212 KB answer = YES
34 Correct 1 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 1 ms 212 KB answer = YES
38 Correct 1 ms 212 KB answer = YES
39 Correct 2 ms 340 KB answer = YES
40 Correct 4 ms 340 KB answer = YES
41 Correct 3 ms 340 KB answer = NO
42 Correct 4 ms 340 KB answer = YES
43 Correct 5 ms 340 KB answer = YES
44 Correct 4 ms 340 KB answer = YES
45 Correct 4 ms 324 KB answer = YES
46 Correct 2 ms 328 KB answer = YES
47 Correct 4 ms 324 KB answer = YES
48 Correct 4 ms 340 KB answer = YES
49 Correct 46 ms 1268 KB answer = YES
50 Correct 37 ms 1716 KB answer = YES
51 Correct 36 ms 1584 KB answer = YES
52 Correct 34 ms 1564 KB answer = NO
53 Correct 4 ms 340 KB answer = YES
54 Correct 10 ms 460 KB answer = YES
55 Correct 20 ms 724 KB answer = YES
56 Correct 44 ms 1268 KB answer = YES
57 Correct 44 ms 1256 KB answer = YES
58 Correct 39 ms 1176 KB answer = YES
59 Correct 39 ms 1184 KB answer = YES
60 Correct 48 ms 1488 KB answer = YES
61 Correct 20 ms 800 KB answer = YES
62 Correct 277 ms 6080 KB answer = NO
63 Correct 532 ms 6092 KB answer = YES
64 Correct 510 ms 6200 KB answer = NO
65 Correct 500 ms 6076 KB answer = YES
66 Correct 8 ms 468 KB answer = YES

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 316 KB answer = YES
6 Correct 0 ms 320 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 328 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 320 KB answer = YES
16 Correct 0 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 1 ms 316 KB answer = YES
19 Correct 1 ms 316 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 1 ms 316 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 1 ms 212 KB answer = YES
25 Correct 1 ms 320 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 212 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 1 ms 212 KB answer = YES
34 Correct 1 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 1 ms 212 KB answer = YES
38 Correct 1 ms 212 KB answer = YES
39 Correct 2 ms 340 KB answer = YES
40 Correct 4 ms 340 KB answer = YES
41 Correct 3 ms 340 KB answer = NO
42 Correct 4 ms 340 KB answer = YES
43 Correct 5 ms 340 KB answer = YES
44 Correct 4 ms 340 KB answer = YES
45 Correct 4 ms 324 KB answer = YES
46 Correct 2 ms 328 KB answer = YES
47 Correct 4 ms 324 KB answer = YES
48 Correct 4 ms 340 KB answer = YES
49 Correct 46 ms 1268 KB answer = YES
50 Correct 37 ms 1716 KB answer = YES
51 Correct 36 ms 1584 KB answer = YES
52 Correct 34 ms 1564 KB answer = NO
53 Correct 4 ms 340 KB answer = YES
54 Correct 10 ms 460 KB answer = YES
55 Correct 20 ms 724 KB answer = YES
56 Correct 44 ms 1268 KB answer = YES
57 Correct 44 ms 1256 KB answer = YES
58 Correct 39 ms 1176 KB answer = YES
59 Correct 39 ms 1184 KB answer = YES
60 Correct 48 ms 1488 KB answer = YES
61 Correct 20 ms 800 KB answer = YES
62 Correct 277 ms 6080 KB answer = NO
63 Correct 532 ms 6092 KB answer = YES
64 Correct 510 ms 6200 KB answer = NO
65 Correct 500 ms 6076 KB answer = YES
66 Correct 8 ms 468 KB answer = YES
67 Correct 347 ms 14864 KB answer = YES
68 Correct 329 ms 14780 KB answer = YES
69 Correct 334 ms 14776 KB answer = YES
70 Correct 502 ms 17572 KB answer = YES
71 Correct 334 ms 15076 KB answer = YES
72 Execution timed out 1045 ms 9228 KB Time limit exceeded
73 Halted 0 ms 0 KB -