Submission #1273244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273244		cpismylifeOwO	Graph (BOI20_graph)	C++20	100 / 100	114 ms	25172 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];
bool fil[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;
                fil[u] = true;
                val[u] = 0;
                int t = u;
                for (int x = (int)curdfs.size() - 1; x >= 0; x--)
                {
                    if (t == v)
                    {
                        break;
                    }
                    val[u] += edges[curdfs[x]].w * (1 - 2 * neg);
                    neg = !neg;
                    t = t ^ edges[curdfs[x]].u ^ edges[curdfs[x]].v;
                }
                val[u] += edges[x].w * (1 - 2 * neg);
            }
        }
    }
}

bool check;
vector<int> cur;

void DFS1(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];
            DFS1(v);
        }
        else
        {
            check &= (val[u] + val[v] == 2 * edges[x].w);
        }
    }
}

bool isneg[MaxN];

void DFS2(int u)
{
    cur.push_back(u);
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u;
        if (!visited[v])
        {
            visited[v] = true;
            isneg[v] = !isneg[u];
            val[v] = 2 * edges[x].w - val[u];
            DFS2(v);
        }
    }
}

bool cmp(int a, int b)
{
    return val[a] * (1 - 2 * (!isneg[a])) < val[b] * (1 - 2 * (!isneg[b]));
}

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        fil[x] = false;
        visited[x] = false;
    }
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x])
        {
            iscycle = false;
            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] && fil[x])
        {
            visited[x] = true;
            DFS1(x);
        }
    }
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x])
        {
            cur.clear();
            val[x] = 0;
            visited[x] = true;
            isneg[x] = false;
            DFS2(x);
            if (cur.empty())
            {
                val[x] = 0;
                continue;
            }
            sort(cur.begin(), cur.end(), cmp);
            int p = ((int)cur.size() + 1) / 2 - 1;
            val[x] = val[cur[p]] * (1 - 2 * (!isneg[cur[p]]));
            for (int x : cur)
            {
                visited[x] = false;
            }
            visited[x] = true;
            DFS1(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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 42 / 42
• Subtask 5: 5 / 5