oj.uz

Submission #557812

# Submission time Handle Problem Language Result Execution time Memory
557812 2022-05-06T05:02:13 Z Ai7081 Graph (BOI20_graph) C++17
5 / 100
 2 ms 2656 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second

const int N = 1e5 + 5;

int n, m;
double ans[N];
pair<int, int> val[N], x;
bool mark[N], markx, fail;
vector<pair<int, int>> adj[N];
vector<int> a, now;

void dfs(int v) {
    if (fail) return;
    mark[v] = true;
    now.push_back(v);
    for (auto [to, w] : adj[v]) {
        if (mark[to]) {
            if (val[v].nd != val[to].nd) {
                if (val[v].st + val[to].st != w) {fail = true; return;}
            }
            else {
                if (markx) {
                    if (x.nd*(val[v].st+val[to].st) + x.st*(val[v].nd+val[to].nd) != x.nd*w) {
                        fail = true; return;
                    }
                }
                else if (val[v].nd == val[to].nd) {
                    x = {w-(val[v].st+val[to].st), val[v].nd+val[to].nd};
                    markx = true;
                }
            }
        }
        else {
            val[to] = {w-val[v].st, -val[v].nd};
            dfs(to);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
//    scanf(" %d %d", &n, &m);
    cin >> n >> m;
    while (m--) {
        int u, v, w;
//        scanf(" %d %d %d", &u, &v, &w);
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i=1; i<=n; i++) if (!mark[i]) {
        markx = false;
        now.clear();
        val[i] = {0, 1};
        dfs(i);
        if (fail) {/*printf("NO");*/ cout << "NO"; return 0;}
        if (!markx) {
            for (auto i : now) a.push_back(-val[i].nd*val[i].st);
            sort(a.begin(), a.end());
            x = {a[a.size()/2], 1};
        }
        for (auto i : now) ans[i] = (double)(x.st*val[i].nd+x.nd*val[i].st) / (double)x.nd;
    }
//    printf("YES\n");
//    for (int i=1; i<=n; i++) printf("%lf ", ans[i]);
    cout << "YES\n";
    for (int i=1; i<=n; i++) cout << ans[i] << ' ';
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2656 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2596 KB answer = YES
25 Correct 2 ms 2588 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2644 KB answer = YES
34 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
35 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2656 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2596 KB answer = YES
25 Correct 2 ms 2588 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2644 KB answer = YES
34 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
35 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2656 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2596 KB answer = YES
25 Correct 2 ms 2588 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2644 KB answer = YES
34 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
35 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2656 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 2 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 1 ms 2644 KB answer = NO
13 Correct 1 ms 2644 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 1 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2596 KB answer = YES
25 Correct 2 ms 2588 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 2 ms 2644 KB answer = YES
34 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
35 Halted 0 ms 0 KB -