oj.uz

Submission #726418

# Submission time Handle Problem Language Result Execution time Memory
726418 2023-04-18T21:46:38 Z YENGOYAN Graph (BOI20_graph) C++14
34 / 100
 700 ms 6164 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 = 1e18;
     
    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 *= 10;
        gp[--u].push_back({--v, w});
        gp[v].push_back({u, w});
      }
      vector<LL> ans(n, inf), val(n), comp;
      vector<bool> vis;
      LL sm = 0;
      function<void(int)> dfs = [&](int u){
        vis[u] = 1;
        if(sm != inf) {
          sm += abs(val[u]);
        }
        comp.push_back(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<double> res(n);
      vector<int> st;
      for(int a = -100; a <= 100; ++a){
        vis = vector<bool> (n);
        val = vector<LL> (n);
        for(int i = 0; i < n; ++i) {
          if(vis[i]) {
            continue;
          }
          if(a == -100) {
            st.push_back(i);
          }
          sm = 0;
          val[i] = a;
          comp.clear();
          dfs(i);
          if(sm < ans[i]) {
            ans[i] = sm;
            for(LL &u : comp) {
              res[u] = val[u];
            }
          }
        }
      }
      for(int &u : st){
        if(ans[u] == inf){ 
          cout << "NO\n";
          return;
        }
      }
      cout << "YES\n";
      for(int i = 0; i < n; ++i) {
        cout << double(res[i] / 10) << " ";
      }
      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 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 1 ms 212 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 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 1 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 2 ms 212 KB answer = YES
25 Correct 1 ms 212 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 2 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 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 1 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 2 ms 212 KB answer = YES
25 Correct 1 ms 212 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 2 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 2 ms 212 KB answer = YES
38 Correct 1 ms 212 KB answer = YES
39 Correct 4 ms 340 KB answer = YES
40 Correct 7 ms 436 KB answer = YES
41 Correct 6 ms 340 KB answer = NO
42 Correct 6 ms 340 KB answer = YES
43 Correct 8 ms 340 KB answer = YES
44 Correct 7 ms 340 KB answer = YES
45 Correct 7 ms 340 KB answer = YES
46 Correct 4 ms 340 KB answer = YES
47 Correct 6 ms 432 KB answer = YES
48 Correct 7 ms 340 KB answer = YES

Subtask #4
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 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 1 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 2 ms 212 KB answer = YES
25 Correct 1 ms 212 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 2 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 2 ms 212 KB answer = YES
38 Correct 1 ms 212 KB answer = YES
39 Correct 4 ms 340 KB answer = YES
40 Correct 7 ms 436 KB answer = YES
41 Correct 6 ms 340 KB answer = NO
42 Correct 6 ms 340 KB answer = YES
43 Correct 8 ms 340 KB answer = YES
44 Correct 7 ms 340 KB answer = YES
45 Correct 7 ms 340 KB answer = YES
46 Correct 4 ms 340 KB answer = YES
47 Correct 6 ms 432 KB answer = YES
48 Correct 7 ms 340 KB answer = YES
49 Correct 114 ms 1396 KB answer = YES
50 Correct 89 ms 1720 KB answer = YES
51 Correct 84 ms 1748 KB answer = YES
52 Correct 70 ms 1748 KB answer = NO
53 Correct 8 ms 432 KB answer = YES
54 Correct 17 ms 548 KB answer = YES
55 Correct 44 ms 884 KB answer = YES
56 Correct 97 ms 1376 KB answer = YES
57 Correct 92 ms 1296 KB answer = YES
58 Correct 81 ms 1264 KB answer = YES
59 Correct 72 ms 1268 KB answer = YES
60 Correct 99 ms 1372 KB answer = YES
61 Correct 40 ms 880 KB answer = YES
62 Correct 499 ms 6164 KB answer = NO
63 Execution timed out 958 ms 6044 KB Time limit exceeded
64 Halted 0 ms 0 KB -

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 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 1 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 2 ms 212 KB answer = YES
25 Correct 1 ms 212 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 2 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 2 ms 212 KB answer = YES
38 Correct 1 ms 212 KB answer = YES
39 Correct 4 ms 340 KB answer = YES
40 Correct 7 ms 436 KB answer = YES
41 Correct 6 ms 340 KB answer = NO
42 Correct 6 ms 340 KB answer = YES
43 Correct 8 ms 340 KB answer = YES
44 Correct 7 ms 340 KB answer = YES
45 Correct 7 ms 340 KB answer = YES
46 Correct 4 ms 340 KB answer = YES
47 Correct 6 ms 432 KB answer = YES
48 Correct 7 ms 340 KB answer = YES
49 Correct 114 ms 1396 KB answer = YES
50 Correct 89 ms 1720 KB answer = YES
51 Correct 84 ms 1748 KB answer = YES
52 Correct 70 ms 1748 KB answer = NO
53 Correct 8 ms 432 KB answer = YES
54 Correct 17 ms 548 KB answer = YES
55 Correct 44 ms 884 KB answer = YES
56 Correct 97 ms 1376 KB answer = YES
57 Correct 92 ms 1296 KB answer = YES
58 Correct 81 ms 1264 KB answer = YES
59 Correct 72 ms 1268 KB answer = YES
60 Correct 99 ms 1372 KB answer = YES
61 Correct 40 ms 880 KB answer = YES
62 Correct 499 ms 6164 KB answer = NO
63 Execution timed out 958 ms 6044 KB Time limit exceeded
64 Halted 0 ms 0 KB -