oj.uz

Submission #958130

# Submission time Handle Problem Language Result Execution time Memory
958130 2024-04-05T01:54:38 Z kanpham Graph (BOI20_graph) C++14
0 / 100
 2 ms 4188 KB 
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int MAX = 1e5+2;
const double err = 1e-6;

int n;
vector<array<int,2>> g[MAX];
bool vis[MAX];
double ans[MAX];
complex<int> linear[MAX];

void sakujo(){
    cout << "NO";
    exit(0);
}

vector<int> hist;
double key;
void dfs(int s){
    vis[s] = true;
    hist.push_back(s);

    for (auto e:g[s]){
        int v = e[0];
        complex<int> sum = {e[1], 0};
        if (vis[v]){
            int a1 = linear[v].real(), a2 = linear[s].real(), b1 = linear[v].imag(), b2 = linear[s].imag();
            if (b1 + b2 == 0){
                if (a1 + a2 == e[1]) continue;
                sakujo();
            }
            key = ((double)e[1] - a1 - a2) / ((double)b1 + b2);
            continue;
        }
        linear[v] = sum - linear[s];
        dfs(v);
    }
}

void calc(int s, double val){
    vis[s] = true;
    ans[s] = linear[s].real() + linear[s].imag() * val;

    for (auto e:g[s]){
        int v = e[0];
        if (!vis[v]) calc(v, val);
    }
}

void verify(int s){
    vis[s] = true;
    for (auto e:g[s]){
        int v = e[0];
        double sum = e[1];
        if (abs(ans[s] + ans[v] - sum) > err) sakujo();
        if (!vis[v]) verify(v);
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

   

    int m;
    cin >> n >> m;
    while (m--){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }

    for (int i=1; i<=n; ++i){
        if (!vis[i]){
            hist.clear();
            linear[i] = {0, 1};
            dfs(i);

            for (int v:hist) vis[v] = false;
            calc(i, key);

            for (int v:hist) vis[v] = false;
            verify(i);
        }
    }

    cout << "YES\n" << setprecision(6);
    for (int i=1; i<=n; ++i) cout << ans[i] << ' ';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB answer = YES
2 Correct 1 ms 4188 KB answer = YES
3 Correct 1 ms 4188 KB answer = YES
4 Correct 1 ms 4188 KB answer = NO
5 Correct 1 ms 4188 KB answer = YES
6 Incorrect 1 ms 4188 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB answer = YES
2 Correct 1 ms 4188 KB answer = YES
3 Correct 1 ms 4188 KB answer = YES
4 Correct 1 ms 4188 KB answer = NO
5 Correct 1 ms 4188 KB answer = YES
6 Incorrect 1 ms 4188 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB answer = YES
2 Correct 1 ms 4188 KB answer = YES
3 Correct 1 ms 4188 KB answer = YES
4 Correct 1 ms 4188 KB answer = NO
5 Correct 1 ms 4188 KB answer = YES
6 Incorrect 1 ms 4188 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB answer = YES
2 Correct 1 ms 4188 KB answer = YES
3 Correct 1 ms 4188 KB answer = YES
4 Correct 1 ms 4188 KB answer = NO
5 Correct 1 ms 4188 KB answer = YES
6 Incorrect 1 ms 4188 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB answer = YES
2 Correct 1 ms 4188 KB answer = YES
3 Correct 1 ms 4188 KB answer = YES
4 Correct 1 ms 4188 KB answer = NO
5 Correct 1 ms 4188 KB answer = YES
6 Incorrect 1 ms 4188 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -