oj.uz

Submission #726384

# Submission time Handle Problem Language Result Execution time Memory
726384 2023-04-18T20:09:49 Z Johann Graph (BOI20_graph) C++14
100 / 100
 175 ms 20092 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

int N, M;
vvpii adj;
vi vis;
vpii poly;
vi newNodes;
vector<int> ans;
bool possible = true;
bool xdefined = false;
int x = 0;

void dfs(int v)
{
    vis[v] = true;
    newNodes.push_back(v);

    int u, c;
    for (pii e : adj[v])
    {
        tie(u, c) = e;
        if (vis[u])
        {
            // check whether cohrerent possible
            pii res = {poly[v].first + poly[u].first, poly[v].second + poly[u].second};
            if (res.first == c && res.second == 0)
            {
                // perfect, nothing to do
            }
            else if (xdefined)
            {
                if (res.first + res.second * x - c != 0)
                    possible = false;
            }
            else
            {
                // not x defined
                if (res.second == 0)
                    possible = false;
                else
                {
                    xdefined = true;
                    assert((c - res.first) % res.second == 0);
                    x = (c - res.first) / res.second;
                }
            }
        }
        else
        { // new Node
            poly[u] = {c - poly[v].first, -poly[v].second};
            dfs(u);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    adj.resize(N);
    for (int i = 0, a, b, c; i < M; ++i)
    {
        cin >> a >> b >> c;
        --a, --b, c *= 2;
        adj[a].push_back({b, c}), adj[b].push_back({a, c});
    }

    vis.assign(N, false);
    ans.resize(N);
    poly.resize(N);
    for (int v = 0; v < N; ++v)
        if (!vis[v])
        {
            xdefined = false;
            x = 0;
            poly[v] = {0, 1};
            newNodes.clear();
            dfs(v);

            if (!xdefined)
            {
                int l = INT_MAX, r = INT_MIN;

                for (int w : newNodes)
                {
                    if (poly[w].second != 0)
                    {
                        int xcand = -poly[w].first / poly[w].second;
                        l = min(l, xcand), r = max(r, xcand);
                    }
                }
                // potentiell sogar falsch, falls es nur eine Moegliches x gibt
                x = 0;
                ll minAns = 1LL << 60;
                while (l < r)
                {
                    int m = l + (r - l) / 2;
                    ll e1 = 0, e2 = 0;
                    for (int u : newNodes)
                    {
                        e1 += (ll)abs(poly[u].first + poly[u].second * m);
                        e2 += (ll)abs(poly[u].first + poly[u].second * (m + 1));
                    }
                    if (e1 < minAns)
                        x = m, minAns = e1;
                    if (e2 < minAns)
                        x = m + 1, minAns = e2;

                    if (e1 < e2)
                        r = m;
                    else if (e1 > e2)
                        l = m + 1;
                    else
                        l = m, r = m;
                }
            }

            for (int u : newNodes)
                ans[u] = poly[u].first + poly[u].second * x;
        }

    if (possible)
    {
        cout << "YES\n";
        for (int v = 0; v < N; ++v)
            cout << ans[v] / (double)2 << " ";
        cout << "\n";
    }
    else
    {
        cout << "NO\n";
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 1 ms 312 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 324 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 320 KB answer = YES
12 Correct 1 ms 212 KB answer = NO
13 Correct 1 ms 324 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 316 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 0 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 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 1 ms 312 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 324 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 320 KB answer = YES
12 Correct 1 ms 212 KB answer = NO
13 Correct 1 ms 324 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 316 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 0 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 1 ms 324 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 212 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 1 ms 212 KB answer = YES
34 Correct 1 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 1 ms 312 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 324 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 320 KB answer = YES
12 Correct 1 ms 212 KB answer = NO
13 Correct 1 ms 324 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 316 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 0 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 1 ms 324 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 212 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 1 ms 212 KB answer = YES
34 Correct 1 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 1 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 1 ms 340 KB answer = YES
40 Correct 1 ms 340 KB answer = YES
41 Correct 1 ms 340 KB answer = NO
42 Correct 1 ms 340 KB answer = YES
43 Correct 2 ms 340 KB answer = YES
44 Correct 1 ms 340 KB answer = YES
45 Correct 1 ms 340 KB answer = YES
46 Correct 1 ms 340 KB answer = YES
47 Correct 2 ms 340 KB answer = YES
48 Correct 1 ms 340 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 1 ms 312 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 324 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 320 KB answer = YES
12 Correct 1 ms 212 KB answer = NO
13 Correct 1 ms 324 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 316 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 0 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 1 ms 324 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 212 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 1 ms 212 KB answer = YES
34 Correct 1 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 1 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 1 ms 340 KB answer = YES
40 Correct 1 ms 340 KB answer = YES
41 Correct 1 ms 340 KB answer = NO
42 Correct 1 ms 340 KB answer = YES
43 Correct 2 ms 340 KB answer = YES
44 Correct 1 ms 340 KB answer = YES
45 Correct 1 ms 340 KB answer = YES
46 Correct 1 ms 340 KB answer = YES
47 Correct 2 ms 340 KB answer = YES
48 Correct 1 ms 340 KB answer = YES
49 Correct 9 ms 1340 KB answer = YES
50 Correct 8 ms 1612 KB answer = YES
51 Correct 9 ms 1620 KB answer = YES
52 Correct 5 ms 1492 KB answer = NO
53 Correct 1 ms 340 KB answer = YES
54 Correct 3 ms 468 KB answer = YES
55 Correct 5 ms 724 KB answer = YES
56 Correct 11 ms 1236 KB answer = YES
57 Correct 9 ms 1108 KB answer = YES
58 Correct 7 ms 1108 KB answer = YES
59 Correct 7 ms 1108 KB answer = YES
60 Correct 9 ms 1364 KB answer = YES
61 Correct 5 ms 724 KB answer = YES
62 Correct 62 ms 8012 KB answer = NO
63 Correct 68 ms 8160 KB answer = YES
64 Correct 55 ms 8024 KB answer = NO
65 Correct 73 ms 8120 KB answer = YES
66 Correct 2 ms 468 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 1 ms 312 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 324 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 1 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Correct 1 ms 212 KB answer = YES
11 Correct 1 ms 320 KB answer = YES
12 Correct 1 ms 212 KB answer = NO
13 Correct 1 ms 324 KB answer = YES
14 Correct 0 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 316 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 0 ms 212 KB answer = YES
22 Correct 1 ms 212 KB answer = NO
23 Correct 1 ms 212 KB answer = NO
24 Correct 1 ms 324 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 212 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 1 ms 212 KB answer = YES
34 Correct 1 ms 212 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 1 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 1 ms 340 KB answer = YES
40 Correct 1 ms 340 KB answer = YES
41 Correct 1 ms 340 KB answer = NO
42 Correct 1 ms 340 KB answer = YES
43 Correct 2 ms 340 KB answer = YES
44 Correct 1 ms 340 KB answer = YES
45 Correct 1 ms 340 KB answer = YES
46 Correct 1 ms 340 KB answer = YES
47 Correct 2 ms 340 KB answer = YES
48 Correct 1 ms 340 KB answer = YES
49 Correct 9 ms 1340 KB answer = YES
50 Correct 8 ms 1612 KB answer = YES
51 Correct 9 ms 1620 KB answer = YES
52 Correct 5 ms 1492 KB answer = NO
53 Correct 1 ms 340 KB answer = YES
54 Correct 3 ms 468 KB answer = YES
55 Correct 5 ms 724 KB answer = YES
56 Correct 11 ms 1236 KB answer = YES
57 Correct 9 ms 1108 KB answer = YES
58 Correct 7 ms 1108 KB answer = YES
59 Correct 7 ms 1108 KB answer = YES
60 Correct 9 ms 1364 KB answer = YES
61 Correct 5 ms 724 KB answer = YES
62 Correct 62 ms 8012 KB answer = NO
63 Correct 68 ms 8160 KB answer = YES
64 Correct 55 ms 8024 KB answer = NO
65 Correct 73 ms 8120 KB answer = YES
66 Correct 2 ms 468 KB answer = YES
67 Correct 79 ms 15844 KB answer = YES
68 Correct 78 ms 15852 KB answer = YES
69 Correct 72 ms 15684 KB answer = YES
70 Correct 103 ms 20092 KB answer = YES
71 Correct 76 ms 15788 KB answer = YES
72 Correct 95 ms 10028 KB answer = YES
73 Correct 102 ms 10028 KB answer = YES
74 Correct 52 ms 9532 KB answer = YES
75 Correct 33 ms 9288 KB answer = NO
76 Correct 10 ms 1492 KB answer = YES
77 Correct 20 ms 2820 KB answer = YES
78 Correct 34 ms 4564 KB answer = YES
79 Correct 77 ms 8568 KB answer = YES
80 Correct 54 ms 9512 KB answer = YES
81 Correct 44 ms 12528 KB answer = NO
82 Correct 91 ms 15428 KB answer = YES
83 Correct 110 ms 15744 KB answer = YES
84 Correct 95 ms 15692 KB answer = YES
85 Correct 80 ms 15788 KB answer = YES
86 Correct 79 ms 15804 KB answer = YES
87 Correct 55 ms 11136 KB answer = NO
88 Correct 108 ms 12088 KB answer = YES
89 Correct 99 ms 8988 KB answer = YES
90 Correct 77 ms 8892 KB answer = YES
91 Correct 88 ms 8908 KB answer = YES
92 Correct 44 ms 5280 KB answer = YES
93 Correct 37 ms 5204 KB answer = YES
94 Correct 57 ms 15428 KB answer = NO
95 Correct 55 ms 8620 KB answer = NO
96 Correct 175 ms 17896 KB answer = YES
97 Correct 38 ms 15424 KB answer = NO