Submission #764483

#	Time	Username	Problem	Language	Result	Execution time	Memory
764483		anaduguleanu	Graph (BOI20_graph)	C++14	100 / 100	107 ms	20464 KiB

Graph

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <pair <int, int>> graph[MAX + 10];
pair <int, double> ans[MAX + 10];
vector <int> nodes;
vector <double> aux;
int visited[MAX + 10], possible, foundX;
double x;
void speedy()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void dfs(int node)
{
    if (possible == 1)
    {
        visited[node] = 1;
        nodes.push_back(node);
        for (auto it : graph[node])
        {
            int a = -ans[node].first, b;
            if (it.second == 1)
                b = 1.0 - ans[node].second;
            else
                b = 2.0 - ans[node].second;
            if (visited[it.first] == 0)
            {
                ans[it.first] = {a, b};
                dfs(it.first);
            }
            else
                if (a == ans[it.first].first && b == ans[it.first].second)
                {

                }
                else
                    if (a == ans[it.first].first && b != ans[it.first].second)
                        possible = 0;
                    else
                    {
                        foundX = 1;
                        x = (ans[it.first].second - b) / (a - ans[it.first].first);
                    }

        }
    }
}
int main()
{
    speedy();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    possible = 1;
    for (int i = 1; i <= n && possible == 1; i++)
        if (visited[i] == 0)
        {
            ans[i] = {1, 0.0};
            foundX = 0;
            dfs(i);
            if (foundX == 0)
            {
                for (auto node : nodes)
                    aux.push_back(-ans[node].first * ans[node].second);
                sort(aux.begin(), aux.end());
                x = aux[aux.size() / 2];
            }
            for (auto node : nodes)
                ans[node] = {0, ans[node].first * x + ans[node].second};
            if (possible == 1)
                for (auto node : nodes)
                    for (auto it : graph[node])
                        if (ans[node].second + ans[it.first].second != it.second)
                            possible = 0;
            aux.clear();
            nodes.clear();
        }
    if (possible == 1)
    {
        cout << "YES\n";
        for (int i = 1; i <= n; i++)
            cout << ans[i].second << ' ';
    }
    else
        cout << "NO\n";
    return 0;
}

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