제출 #1273231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273231		cpismylifeOwO	Graph (BOI20_graph)	C++20	0 / 100	5 ms	344 KiB

Graph

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

struct Edge
{
    int u, v, w;
    bool isused;
};

int n, m;
Edge edges[MaxN];
vector<int> graph[MaxN];

void Inp()
{
    cin >> n >> m;
    for (int x = 1; x <= m; x++)
    {
        cin >> edges[x].u >> edges[x].v >> edges[x].w;
        graph[edges[x].u].push_back(x);
        graph[edges[x].v].push_back(x);
    }
}

bool iscycle;
bool visited[MaxN];
long long val[MaxN];
int h[MaxN];
vector<int> curdfs;

void PreDFS(int u)
{
    for (int x : graph[u])
    {
        if (edges[x].isused)
        {
            continue;
        }
        int v = edges[x].u ^ edges[x].v ^ u;
        edges[x].isused = true;
        if (!visited[v])
        {
            curdfs.push_back(x);
            h[v] = h[u] + 1;
            visited[v] = true;
            PreDFS(v);
            curdfs.pop_back();
        }
        else
        {
            if (!iscycle && (h[u] - h[v]) % 2 == 0)
            {
                iscycle = true;
                bool neg = false;
                val[u] = 0;
                int t = u;
                for (int x = (int)curdfs.size() - 1; x >= 0; x--)
                {
                    val[u] += edges[curdfs[x]].w * (1 - 2 * neg);
                    neg = !neg;
                    t = t ^ edges[curdfs[x]].u ^ edges[curdfs[x]].v;
                    if (t == v)
                    {
                        break;
                    }
                }
                val[u] += edges[x].w * (1 - 2 * neg);
            }
        }
    }
}

bool check;

void DFS(int u)
{
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u;
        if (!visited[v])
        {
            visited[v] = true;
            val[v] = 2 * edges[x].w - val[u];
            DFS(v);
        }
        else
        {
            check &= (val[u] + val[v] == 2 * edges[x].w);
        }
    }
}

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        val[x] = -1;
        visited[x] = false;
    }
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x])
        {
            visited[x] = true;
            PreDFS(x);
        }
    }
    for (int x = 1; x <= n; x++)
    {
        visited[x] = false;
    }
    check = true;
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x] && ~val[x])
        {
            visited[x] = true;
            DFS(x);
        }
    }
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x])
        {
            val[x] = 0;
            visited[x] = true;
            DFS(x);
        }
    }
    if (!check)
    {
        cout << "NO";
        return;
    }
    cout << "YES\n";
    for (int x = 1; x <= n; x++)
    {
        cout << fixed << setprecision(6) << (long double)((long double)val[x] / 2.0) << " ";
    }
}

int main()
{
    //freopen("GRAPH.INP", "r", stdin);
    //freopen("GRAPH.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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