Submission #1100524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100524		vjudge1	Graph (BOI20_graph)	C++17	100 / 100	159 ms	24196 KiB

Graph

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair <int, int> pii;

const int INF = 1e9;
const int MAXN = 2e5 + 10;

bool d1[MAXN];
int d2[MAXN];
int cost[MAXN];
bool mark1[MAXN];
bool mark2[MAXN];
vector <pii> e[MAXN];
vector <int> vec;

void dfs1(int v, int val)
{
    mark1[v] = true;
    cost[v] = val;
    for (auto [u, w] : e[v])
    {
        if (mark1[u])
        {
            if (cost[v] + cost[u] != 2 * w)
            {
                cout << "NO" << endl;
                exit(0);
            }
        }
        else
        {
            dfs1(u, 2 * w - val);
        }
    }
}

int dfs2(int v)
{
    mark2[v] = true;
    vec.push_back((d1[v] ? d2[v] : -d2[v]));
    for (auto [u, w] : e[v])
    {
            if (!mark2[u])
            {
                d1[u] = !d1[v];
                d2[u] = 2 * w - d2[v];
                int x = dfs2(u);
                if (x < INF)
                    return x;
            }
            else
            {
                if (d1[v] ^ d1[u])
                {
                    if (2 * w - d2[v] != d2[u])
                    {
                        cout << "NO" << endl;
                        exit(0);
                    }
                }
                else
                {
                    return (w - (d2[v] + d2[u]) / 2) * (d1[v] ? -1 : 1);
                }
            }
    }
    return INF;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int v, u, w;
        cin >> v >> u >> w;
        e[v].push_back({u, w});
        e[u].push_back({v, w});
    }
    for (int i = 1; i <= n; i++)
    {
        if (mark1[i])
            continue;
        int x = dfs2(i);
        if (x == INF)
        {
            sort(vec.begin(), vec.end());
            x = vec[(vec.size() / 2)];
        }
        dfs1(i, x);
        vec.clear();
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++)
        cout << (float) (cost[i] / (float) 2) << " ";
    cout << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42