oj.uz

답안 #651593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651593 2022-10-19T11:55:48 Z 1zaid1 Graph (BOI20_graph) C++17
0 / 100
 22 ms 35688 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n';

const int M = 5e5+5, MOD = 1e9+7;
vector<int> node[M], tmp;
vector<array<int, 3>> v;
int p[M], d[M], loop;
bitset<500005> vis;
map<int, int> e[M];
double cost[M];

void dfs(int s, int dp = 0) {
    vis[s] = 1;
    d[s] = dp++;
    tmp.push_back(s);

    for (int i:node[s]) {
        if (!vis[i]) {
            p[i] = s;
            dfs(i, dp);
        } else if (!loop&&(dp-d[i])%2) {
            p[i] = s;
            loop = s;
            return;
        }
    }
}

double eval(int s, double a) {
    double ans = a;
    cost[s] = a;
    vis[s] = 1;
    for (int i:node[s]) if (!vis[i]) ans += abs(eval(i, e[s][i]-a));
    return ans;
}

bool check(vector<int> x) {
    for (auto i:x)
        for (int j:node[i])
            if (abs(cost[i] + cost[j] - e[i][j]) >= 1e-6) return 0;
    return true;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (e[a][b] && e[a][b] != c) {
            cout << "NO" << endl;
            return 0;
        }

        e[a][b] = c;
        e[b][a] = c;
        node[a].push_back(b);
        node[b].push_back(a);
        v.push_back({a, b, c});
    }

    for (int k = 1; k <= n; k++) {
        if (!vis[k]) {
            dfs(k);
            if (loop) {
                int x = loop;
                vector<int> l = {x};
                while (p[x] != loop) {
                    l.push_back(x=p[x]);
                } l.push_back(l[0]);

                double sum = 0;
                for (int i = 0, f = 1; i < l.size()-1; i++, f^=1) {
                    if (f) sum += e[l[i]][l[i+1]];
                    else sum -= e[l[i]][l[i+1]];
                }

                vis = 0;
                eval(loop, sum/2);
                // cout << "LOOP " << loop <<' '<< sum << endl;
            } else {
                vis = 0;
                eval(k, 0);
                if (!check(tmp)) {
                    cout << "NO" << endl;
                    return 0;
                }

                double l = -1e10, r = 1e10, cnt = 0;
                while (abs(r-l) >= 1e-7 && cnt++<100) {
                    double ll = (2*l+r)/3;
                    double rr = (l+2*r)/3;
                    vis = 0; double x = eval(k, ll);
                    vis = 0; double y = eval(k, rr);
                    if (x >= y) l = ll;
                    else r = rr;
                } vis = 0, eval(k, (l+r)/2);
                // cout << "NO LOOP " << l << endl;
            }

            if (!check(tmp)) {
                cout << "NO" << endl;
                // for (auto [a, b, c]:v) if (abs(cost[a] + cost[b] - c) >= 1e-6) cout << cost[a] << ' ' << cost[b] << ' ' << c << endl;
                return 0;
            }

            tmp.clear();
        }
    }

    cout << "YES" << fixed << setprecision(6) << endl;
    for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;

    return 0;
}

/*
4 4
1 2 1
2 3 2
1 3 2
3 4 1

2 1
1 2 1

3 2
1 2 2
2 3 2

3 4
1 2 2
2 2 1
2 1 1
1 2 2
*/

Compilation message

Graph.cpp: In function 'int main()':
Graph.cpp:78:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for (int i = 0, f = 1; i < l.size()-1; i++, f^=1) {
      |                                        ~~^~~~~~~~~~~~
Graph.cpp:117:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  117 |     for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
      |     ^~~
Graph.cpp:117:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  117 |     for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
      |                                                          ^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 35668 KB answer = YES
2 Correct 20 ms 35688 KB answer = YES
3 Correct 17 ms 35668 KB answer = YES
4 Correct 17 ms 35516 KB answer = NO
5 Incorrect 22 ms 35584 KB participant answer is larger than the answer of jury
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 35668 KB answer = YES
2 Correct 20 ms 35688 KB answer = YES
3 Correct 17 ms 35668 KB answer = YES
4 Correct 17 ms 35516 KB answer = NO
5 Incorrect 22 ms 35584 KB participant answer is larger than the answer of jury
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 35668 KB answer = YES
2 Correct 20 ms 35688 KB answer = YES
3 Correct 17 ms 35668 KB answer = YES
4 Correct 17 ms 35516 KB answer = NO
5 Incorrect 22 ms 35584 KB participant answer is larger than the answer of jury
6 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 35668 KB answer = YES
2 Correct 20 ms 35688 KB answer = YES
3 Correct 17 ms 35668 KB answer = YES
4 Correct 17 ms 35516 KB answer = NO
5 Incorrect 22 ms 35584 KB participant answer is larger than the answer of jury
6 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 35668 KB answer = YES
2 Correct 20 ms 35688 KB answer = YES
3 Correct 17 ms 35668 KB answer = YES
4 Correct 17 ms 35516 KB answer = NO
5 Incorrect 22 ms 35584 KB participant answer is larger than the answer of jury
6 Halted 0 ms 0 KB -