oj.uz

Submission #575864

# Submission time Handle Problem Language Result Execution time Memory
575864 2022-06-11T11:44:39 Z talant117408 Graph (BOI20_graph) C++17
34 / 100
 700 ms 27488 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

void solve() {
    int n, m;
    cin >> n >> m;
    vector <vector <pair <int, int>>> graph(n+1);
    vector <pair <pii, int>> edges;
    for (int i = 1; i <= m; i++) {
        int a, b;
        int c;
        cin >> a >> b >> c;
        c *= 10;
        edges.pb(mp(mp(a, b), c));
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }   
    const int range = 301;
    vector <vector <bool>> can(n+1, vector <bool> (range, 1));
    vector <vector <int>> value(n+1, vector <int> (range)), sum(n+1, vector <int> (range));
    vector <pii> acc(n+1, mp(2e9, 0));
    
    vector <int> link(n+1), saizu(n+1, 1);
    iota(all(link), 0);
    function <int(int)> find = [&](int n) {
        if (link[n] == n) return n;
        return link[n] = find(link[n]);
    };
    function <void(int, int)> unite = [&](int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (saizu[a] < saizu[b]) swap(a, b);
        saizu[a] += saizu[b];
        link[b] = a;
    };
    for (auto to : edges) {
        auto a = to.first.first, b = to.first.second;
        unite(a, b);
    }
    
    vector <int> used(n+1);
    function <void(int, int, int)> dfs = [&](int v, int val, int i) {
        value[v][i] = val;
        used[v] = 1;
        for (auto to : graph[v]) {
            if (used[to.first]) continue;
            dfs(to.first, to.second-val, i);
        }
    }; 
    
    set <int> reps;
    for (int i = 1; i <= n; i++) reps.insert(find(i));
    for (int j = 0; j < range; j++) {
        for (int i = 1; i <= n; i++) {
            if (i == find(i)) {
                dfs(i, (j-range/2), j);
            }
        }
        for (int i = 1; i <= n; i++) {
            sum[find(i)][j] += fabs(value[i][j]);
        }
        for (auto to : edges) {
            auto a = to.first.first, b = to.first.second;
            auto c = to.second;
            auto rep = find(a);
            if (fabs(c-value[a][j]-value[b][j]) > 1e-9) {
                can[rep][j] = 0;
            }
        }
        fill(all(used), 0);
        for (auto to : reps) {
            if (can[to][j]) {
                if (acc[to].first > sum[to][j]) {
                    acc[to].first = sum[to][j];
                    acc[to].second = j;
                }
            }
        }
    }
    int ans = 0;
    for (auto to : reps) {
        ans += acc[to].first;
    }
    if (ans >= 2e9) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++) {
        cout << fixed << setprecision(6) << double(value[i][acc[find(i)].second])*.1 << ' ';
    }
}

int main() {
    //~ do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
7
4 2
5 7
3 4
6 3
1 3
4 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 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 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 2 ms 468 KB answer = YES
25 Correct 1 ms 340 KB answer = YES
26 Correct 2 ms 468 KB answer = YES
27 Correct 2 ms 468 KB answer = YES
28 Correct 2 ms 468 KB answer = YES
29 Correct 3 ms 468 KB answer = YES
30 Correct 3 ms 468 KB answer = NO
31 Correct 2 ms 468 KB answer = YES
32 Correct 2 ms 468 KB answer = YES
33 Correct 2 ms 468 KB answer = YES
34 Correct 3 ms 468 KB answer = YES
35 Correct 2 ms 468 KB answer = YES
36 Correct 2 ms 468 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 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 2 ms 468 KB answer = YES
25 Correct 1 ms 340 KB answer = YES
26 Correct 2 ms 468 KB answer = YES
27 Correct 2 ms 468 KB answer = YES
28 Correct 2 ms 468 KB answer = YES
29 Correct 3 ms 468 KB answer = YES
30 Correct 3 ms 468 KB answer = NO
31 Correct 2 ms 468 KB answer = YES
32 Correct 2 ms 468 KB answer = YES
33 Correct 2 ms 468 KB answer = YES
34 Correct 3 ms 468 KB answer = YES
35 Correct 2 ms 468 KB answer = YES
36 Correct 2 ms 468 KB answer = YES
37 Correct 5 ms 852 KB answer = YES
38 Correct 5 ms 724 KB answer = YES
39 Correct 11 ms 1728 KB answer = YES
40 Correct 22 ms 2644 KB answer = YES
41 Correct 20 ms 2644 KB answer = NO
42 Correct 20 ms 2676 KB answer = YES
43 Correct 21 ms 2892 KB answer = YES
44 Correct 22 ms 2892 KB answer = YES
45 Correct 23 ms 2900 KB answer = YES
46 Correct 11 ms 1604 KB answer = YES
47 Correct 22 ms 2908 KB answer = YES
48 Correct 22 ms 2904 KB answer = YES

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 2 ms 468 KB answer = YES
25 Correct 1 ms 340 KB answer = YES
26 Correct 2 ms 468 KB answer = YES
27 Correct 2 ms 468 KB answer = YES
28 Correct 2 ms 468 KB answer = YES
29 Correct 3 ms 468 KB answer = YES
30 Correct 3 ms 468 KB answer = NO
31 Correct 2 ms 468 KB answer = YES
32 Correct 2 ms 468 KB answer = YES
33 Correct 2 ms 468 KB answer = YES
34 Correct 3 ms 468 KB answer = YES
35 Correct 2 ms 468 KB answer = YES
36 Correct 2 ms 468 KB answer = YES
37 Correct 5 ms 852 KB answer = YES
38 Correct 5 ms 724 KB answer = YES
39 Correct 11 ms 1728 KB answer = YES
40 Correct 22 ms 2644 KB answer = YES
41 Correct 20 ms 2644 KB answer = NO
42 Correct 20 ms 2676 KB answer = YES
43 Correct 21 ms 2892 KB answer = YES
44 Correct 22 ms 2892 KB answer = YES
45 Correct 23 ms 2900 KB answer = YES
46 Correct 11 ms 1604 KB answer = YES
47 Correct 22 ms 2908 KB answer = YES
48 Correct 22 ms 2904 KB answer = YES
49 Correct 312 ms 26324 KB answer = YES
50 Correct 300 ms 26728 KB answer = YES
51 Correct 296 ms 26700 KB answer = YES
52 Correct 289 ms 26600 KB answer = NO
53 Correct 23 ms 2968 KB answer = YES
54 Correct 59 ms 6476 KB answer = YES
55 Correct 138 ms 13320 KB answer = YES
56 Correct 296 ms 25796 KB answer = YES
57 Correct 336 ms 26348 KB answer = YES
58 Correct 255 ms 23752 KB answer = YES
59 Correct 249 ms 23752 KB answer = YES
60 Correct 328 ms 26360 KB answer = YES
61 Correct 140 ms 13268 KB answer = YES
62 Execution timed out 1098 ms 27488 KB Time limit exceeded
63 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 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 2 ms 468 KB answer = YES
25 Correct 1 ms 340 KB answer = YES
26 Correct 2 ms 468 KB answer = YES
27 Correct 2 ms 468 KB answer = YES
28 Correct 2 ms 468 KB answer = YES
29 Correct 3 ms 468 KB answer = YES
30 Correct 3 ms 468 KB answer = NO
31 Correct 2 ms 468 KB answer = YES
32 Correct 2 ms 468 KB answer = YES
33 Correct 2 ms 468 KB answer = YES
34 Correct 3 ms 468 KB answer = YES
35 Correct 2 ms 468 KB answer = YES
36 Correct 2 ms 468 KB answer = YES
37 Correct 5 ms 852 KB answer = YES
38 Correct 5 ms 724 KB answer = YES
39 Correct 11 ms 1728 KB answer = YES
40 Correct 22 ms 2644 KB answer = YES
41 Correct 20 ms 2644 KB answer = NO
42 Correct 20 ms 2676 KB answer = YES
43 Correct 21 ms 2892 KB answer = YES
44 Correct 22 ms 2892 KB answer = YES
45 Correct 23 ms 2900 KB answer = YES
46 Correct 11 ms 1604 KB answer = YES
47 Correct 22 ms 2908 KB answer = YES
48 Correct 22 ms 2904 KB answer = YES
49 Correct 312 ms 26324 KB answer = YES
50 Correct 300 ms 26728 KB answer = YES
51 Correct 296 ms 26700 KB answer = YES
52 Correct 289 ms 26600 KB answer = NO
53 Correct 23 ms 2968 KB answer = YES
54 Correct 59 ms 6476 KB answer = YES
55 Correct 138 ms 13320 KB answer = YES
56 Correct 296 ms 25796 KB answer = YES
57 Correct 336 ms 26348 KB answer = YES
58 Correct 255 ms 23752 KB answer = YES
59 Correct 249 ms 23752 KB answer = YES
60 Correct 328 ms 26360 KB answer = YES
61 Correct 140 ms 13268 KB answer = YES
62 Execution timed out 1098 ms 27488 KB Time limit exceeded
63 Halted 0 ms 0 KB -