Submission #1260504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260504		miniob	Graph (BOI20_graph)	C++20	100 / 100	136 ms	12800 KiB

Graph

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> graph[100007];
bool odw[100007];
int tab1[100007];
int tab2[100007];
long double odp[100007];

int main() 
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    for (int i = 1; i <= n; i++) 
    {
        if (!odw[i]) 
        {
            queue<int> q;
            odw[i] = 1;
            tab1[i] = 1;
            tab2[i] = 0;
            q.push(i);
            vector<int> spojn;
            spojn.push_back(i);
			bool czyzdef = false;
			int gdzie = 0;
            while (!q.empty()) 
            {
                int cur = q.front();
                q.pop();
                for (auto x : graph[cur]) 
                {
                    if (!odw[x.first]) 
                    {
                        odw[x.first] = 1;
                        tab1[x.first] = -tab1[cur];
                        tab2[x.first] = x.second - tab2[cur];
                        q.push(x.first);
                        spojn.push_back(x.first);
                    }
                    else 
                    {
                        if (tab1[cur] + tab1[x.first] == 0)
                        {
                            if (tab2[cur] + tab2[x.first] != x.second) 
                            {
                                cout << "NO" << endl;
                                return 0;
                            }
                        }
                        else 
                        {
                        	int gdzie2;
                        	if(tab1[cur] + tab1[x.first] == 2)
                        	{
                        		gdzie2 = x.second - tab2[cur] - tab2[x.first];
                        	}
                        	else
                        	{
                        		gdzie2 = tab2[cur] + tab2[x.first] - x.second;
                        	}
                            if (!czyzdef) 
                            {
                                czyzdef = true;
                                gdzie = gdzie2;
                            } 
                            else if (gdzie != gdzie2) 
                            {
                                cout << "NO" << endl;
                                return 0;
                            }
                        }
                    }
                }
            }
            long double x;
            if (czyzdef)
            {
                x = (long double)gdzie / 2.0;
            }
            else
            {
                vector<long double> domed;
                for (int y : spojn)
                {
                	domed.push_back(-(long double)tab1[y] * (long double)tab2[y]);
                }
                sort(domed.begin(), domed.end());
                if (domed.size() % 2 == 1)
                {
                	x = domed[domed.size()/2];
                }
                else
                {
                	x = (domed[domed.size()/2 - 1] + domed[domed.size()/2]) / 2.0;
                }
            }
            for (int y : spojn)
            {
                odp[y] = (long double)tab1[y] * x + (long double)tab2[y];
            }
        }
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++) 
    {
        cout << fixed << setprecision(10) << odp[i] << " ";
    }
    cout << endl;
    return 0;
}

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