Submission #726057

#	Time	Username	Problem	Language	Result	Execution time	Memory
726057		Johann	Graph (BOI20_graph)	C++14	100 / 100	168 ms	20164 KiB

Graph

#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)
            {
                ll m = 0, b = 0;
                priority_queue<int> A;
                for (int w : newNodes)
                {
                    if (poly[w].second != 0)
                    {
                        assert(abs(poly[w].second) == 1);
                        int nb, nm;
                        tie(nb, nm) = poly[w];
                        if (poly[w].second < 0)
                            nb *= -1, nm *= -1;
                        b += nb, m += nm;
                        A.push(-nb);
                    }
                }
                x = 0;
                ll minAns = 1LL << 60;
                while (!A.empty())
                {
                    ll res = m * A.top() + b;
                    if (res < minAns)
                        x = A.top(), minAns = res;
                    m -= 2;
                    b += (ll)2 * A.top();
                    A.pop();
                }
            }

            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 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42