oj.uz

Submission #575851

# Submission time Handle Problem Language Result Execution time Memory
575851 2022-06-11T11:34:18 Z talant117408 Graph (BOI20_graph) C++17
34 / 100
 700 ms 66264 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, double>>> graph(n+1);
    vector <pair <pii, double>> edges;
    for (int i = 1; i <= m; i++) {
        int a, b;
        double c;
        cin >> a >> b >> c;
        edges.pb(mp(mp(a, b), c));
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }   
    const int range = 401;
    vector <vector <bool>> can(n+1, vector <bool> (range, 1));
    vector <vector <double>> value(n+1, vector <double> (range)), sum(n+1, vector <double> (range));
    vector <pair <double, int>> 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, double, int)> dfs = [&](int v, double 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)*.1, 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;
                }
            }
        }
    }
    double 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) << value[i][acc[find(i)].second] << ' ';
    }
}

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 1 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 340 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 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 340 KB answer = YES
14 Correct 0 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 1 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 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 1 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 340 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 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 340 KB answer = YES
14 Correct 0 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 1 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 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 3 ms 852 KB answer = YES
25 Correct 2 ms 628 KB answer = YES
26 Correct 3 ms 852 KB answer = YES
27 Correct 3 ms 852 KB answer = YES
28 Correct 3 ms 852 KB answer = YES
29 Correct 3 ms 852 KB answer = YES
30 Correct 3 ms 852 KB answer = NO
31 Correct 3 ms 724 KB answer = YES
32 Correct 2 ms 724 KB answer = YES
33 Correct 3 ms 724 KB answer = YES
34 Correct 4 ms 852 KB answer = YES
35 Correct 3 ms 724 KB answer = YES
36 Correct 3 ms 724 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 340 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 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 340 KB answer = YES
14 Correct 0 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 1 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 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 3 ms 852 KB answer = YES
25 Correct 2 ms 628 KB answer = YES
26 Correct 3 ms 852 KB answer = YES
27 Correct 3 ms 852 KB answer = YES
28 Correct 3 ms 852 KB answer = YES
29 Correct 3 ms 852 KB answer = YES
30 Correct 3 ms 852 KB answer = NO
31 Correct 3 ms 724 KB answer = YES
32 Correct 2 ms 724 KB answer = YES
33 Correct 3 ms 724 KB answer = YES
34 Correct 4 ms 852 KB answer = YES
35 Correct 3 ms 724 KB answer = YES
36 Correct 3 ms 724 KB answer = YES
37 Correct 6 ms 1620 KB answer = YES
38 Correct 6 ms 1620 KB answer = YES
39 Correct 16 ms 3896 KB answer = YES
40 Correct 27 ms 6356 KB answer = YES
41 Correct 26 ms 6356 KB answer = NO
42 Correct 27 ms 6456 KB answer = YES
43 Correct 30 ms 6856 KB answer = YES
44 Correct 30 ms 6828 KB answer = YES
45 Correct 30 ms 6868 KB answer = YES
46 Correct 15 ms 3540 KB answer = YES
47 Correct 31 ms 6740 KB answer = YES
48 Correct 29 ms 6852 KB answer = YES

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 340 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 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 340 KB answer = YES
14 Correct 0 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 1 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 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 3 ms 852 KB answer = YES
25 Correct 2 ms 628 KB answer = YES
26 Correct 3 ms 852 KB answer = YES
27 Correct 3 ms 852 KB answer = YES
28 Correct 3 ms 852 KB answer = YES
29 Correct 3 ms 852 KB answer = YES
30 Correct 3 ms 852 KB answer = NO
31 Correct 3 ms 724 KB answer = YES
32 Correct 2 ms 724 KB answer = YES
33 Correct 3 ms 724 KB answer = YES
34 Correct 4 ms 852 KB answer = YES
35 Correct 3 ms 724 KB answer = YES
36 Correct 3 ms 724 KB answer = YES
37 Correct 6 ms 1620 KB answer = YES
38 Correct 6 ms 1620 KB answer = YES
39 Correct 16 ms 3896 KB answer = YES
40 Correct 27 ms 6356 KB answer = YES
41 Correct 26 ms 6356 KB answer = NO
42 Correct 27 ms 6456 KB answer = YES
43 Correct 30 ms 6856 KB answer = YES
44 Correct 30 ms 6828 KB answer = YES
45 Correct 30 ms 6868 KB answer = YES
46 Correct 15 ms 3540 KB answer = YES
47 Correct 31 ms 6740 KB answer = YES
48 Correct 29 ms 6852 KB answer = YES
49 Correct 431 ms 66028 KB answer = YES
50 Correct 416 ms 66248 KB answer = YES
51 Correct 414 ms 66264 KB answer = YES
52 Correct 411 ms 66196 KB answer = NO
53 Correct 31 ms 7028 KB answer = YES
54 Correct 83 ms 15888 KB answer = YES
55 Correct 219 ms 33228 KB answer = YES
56 Correct 429 ms 64584 KB answer = YES
57 Correct 457 ms 65984 KB answer = YES
58 Correct 365 ms 59452 KB answer = YES
59 Correct 361 ms 59584 KB answer = YES
60 Correct 443 ms 66028 KB answer = YES
61 Correct 202 ms 33156 KB answer = YES
62 Execution timed out 1085 ms 65580 KB Time limit exceeded
63 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 340 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 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 340 KB answer = YES
14 Correct 0 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 1 ms 212 KB answer = YES
19 Correct 1 ms 212 KB answer = YES
20 Correct 1 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 3 ms 852 KB answer = YES
25 Correct 2 ms 628 KB answer = YES
26 Correct 3 ms 852 KB answer = YES
27 Correct 3 ms 852 KB answer = YES
28 Correct 3 ms 852 KB answer = YES
29 Correct 3 ms 852 KB answer = YES
30 Correct 3 ms 852 KB answer = NO
31 Correct 3 ms 724 KB answer = YES
32 Correct 2 ms 724 KB answer = YES
33 Correct 3 ms 724 KB answer = YES
34 Correct 4 ms 852 KB answer = YES
35 Correct 3 ms 724 KB answer = YES
36 Correct 3 ms 724 KB answer = YES
37 Correct 6 ms 1620 KB answer = YES
38 Correct 6 ms 1620 KB answer = YES
39 Correct 16 ms 3896 KB answer = YES
40 Correct 27 ms 6356 KB answer = YES
41 Correct 26 ms 6356 KB answer = NO
42 Correct 27 ms 6456 KB answer = YES
43 Correct 30 ms 6856 KB answer = YES
44 Correct 30 ms 6828 KB answer = YES
45 Correct 30 ms 6868 KB answer = YES
46 Correct 15 ms 3540 KB answer = YES
47 Correct 31 ms 6740 KB answer = YES
48 Correct 29 ms 6852 KB answer = YES
49 Correct 431 ms 66028 KB answer = YES
50 Correct 416 ms 66248 KB answer = YES
51 Correct 414 ms 66264 KB answer = YES
52 Correct 411 ms 66196 KB answer = NO
53 Correct 31 ms 7028 KB answer = YES
54 Correct 83 ms 15888 KB answer = YES
55 Correct 219 ms 33228 KB answer = YES
56 Correct 429 ms 64584 KB answer = YES
57 Correct 457 ms 65984 KB answer = YES
58 Correct 365 ms 59452 KB answer = YES
59 Correct 361 ms 59584 KB answer = YES
60 Correct 443 ms 66028 KB answer = YES
61 Correct 202 ms 33156 KB answer = YES
62 Execution timed out 1085 ms 65580 KB Time limit exceeded
63 Halted 0 ms 0 KB -