oj.uz

Submission #557811

# Submission time Handle Problem Language Result Execution time Memory
557811 2022-05-06T05:01:45 Z Ai7081 Graph (BOI20_graph) C++17
0 / 100
 2 ms 2644 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Expected double, but "0.50.51.5-0.5" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Expected double, but "0.50.51.5-0.5" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Expected double, but "0.50.51.5-0.5" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Expected double, but "0.50.51.5-0.5" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Expected double, but "0.50.51.5-0.5" found
2 Halted 0 ms 0 KB -