Submission #1100330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100330		MateiKing80	Graph (BOI20_graph)	C++14	100 / 100	108 ms	23240 KiB

Graph

#include <bits/stdc++.h>

using namespace std ;

const int NMAX = 1e5;

int arr[NMAX + 5];
int n, m;

vector<vector<pair<int, int>>> adj(NMAX + 5);

int vis[NMAX + 5];
int a[NMAX + 5], b[NMAX + 5];

int known = -1;
bool flag = true;

int ans[NMAX + 5];

vector<int>v;

void dfs(int node)
{
    vis[node] = 1;
    v.push_back(a[node] * (-1 * b[node]));
    for(auto &childd : adj[node])
    {
        int child = childd.first, w = childd.second;
        if(vis[child])
        {
            if(b[node] + b[child] != 0)
            {
                int x = (w - a[node] - a[child]) / (b[node] + b[child]);
                ans[node] = a[node] + x * b[node];
                known = node;
            }
            else if(a[node] + a[child] != w)
                flag = false;
            continue;
        }
        a[child] = w - a[node], b[child] = -1 * b[node];
        dfs(child);
    }
}

void dfs2(int node)
{
    vis[node] = 2;
    for(auto &childd : adj[node])
    {
        int child = childd.first, w = childd.second;
        if(vis[child] == 2)
        {
            if(ans[node] + ans[child] != w)
                flag = false;
            continue;
        }
        ans[child] = w - ans[node];
        dfs2(child);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        z *= 2;
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(vis[i])
            continue;
        v.clear(), known = -1;
        b[i] = 1;
        dfs(i);
        if(!flag)
        {
            cout << "NO\n";
            return 0;

        }
        if(known == -1)
        {
            sort(v.begin(), v.end());
            ans[i] = v[v.size() / 2];
            known = i;
        }
        dfs2(known);
        if(!flag)
        {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    for(int i = 1; i <= n; i ++)
        cout << ans[i] / 2.00 << " ";
    cout << "\n";
    return 0;
}

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