Submission #1101924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101924		yoav_s	Graph (BOI20_graph)	C++17	0 / 100	1 ms	560 KiB

Graph

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

p operator+(p &a, p &b)
{
    return p(a.f + b.f, a.s + b.s);
}

p operator-(p &a, p &b)
{
    return p(a.f - b.f, a.s - b.s);
}

bool equal(p &a, p &b)
{
    return a.f * b.s == a.s * b.f;
}

p operator*(p &a, ll b)
{
    return p(a.f * b, a.s * b);
}

void operator-=(p &a, p &b)
{
    a.f -= b.f;
    a.s -= b.s;
}

void operator+=(p &a, p &b)
{
    a.f += b.f;
    a.s += b.f;
}

p operator-(p &a)
{
    return p(-a.f, -a.s);
}

const p zero = p(0, 0);
const p one = p(0, 1);
const p two = p(0, 2);
const p id = p(1, 0);

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vp constants{zero, one, two};
    ll N, M;
    cin >> N >> M;
    vvp graph(N);
    for (ll i = 0; i < M; i++)
    {
        ll a, b , c;
        cin >> a >> b >> c; a--; b--;
        graph[a].eb(b, c);
        graph[b].eb(a, c);
    }
    vb visited(N, false);
    vp function(N);
    vector<double> put(N);
    for (ll i = 0; i < N; i++)
    {
        if (visited[i]) continue;
        vp curFunctions;
        vp constraints;
        stack<tri> dfs;
        v comp;
        dfs.emplace(i, id);
        while (!dfs.empty())
        {
            auto top = dfs.top();
            dfs.pop();
            if (visited[top.f])
            {
                constraints.eb(top.s - function[top.f]);
                continue;
            }
            visited[top.f] = true;
            function[top.f] = top.s;
            comp.pb(top.f);
            curFunctions.pb(top.s);
            for (auto x : graph[top.f]) dfs.emplace(x.f, constants[x.s] - top.s);
        }
        p solution(0, 0);
        for (auto x : constraints)
        {
            if (x.f == 0 && x.s != 0)
            {
                cout << "NO\n";
                return 0;
            }
            else if (x.f != 0)
            {
                if (!equal(solution,x))
                {
                    cout << "NO\n";
                    return 0;
                }
                solution = x;
            }
        }
        double assignment;
        if (solution.f == 0)
        {
            p curFunction(0, 0);
            vector<pair<double, p>> events;
            double minEv = INF;
            double minEvVal = -1;
            for (p x : curFunctions)
            {
                if (x.f >= 0)
                    curFunction += x;
                else
                    curFunction -= x;
                if (x.f != 0)
                {
                    events.eb(-x.s / x.f, x * (x.f >= 0? 1 : -1));
                }
            }
            for (auto x : events)
            {
                if (curFunction.f * x.f + curFunction.s < minEv)
                {
                    minEv = curFunction.f * x.f + curFunction.s;
                    minEvVal = x.f;
                }
                curFunction -= x.s;
                curFunction -= x.s;
            }
            assignment = minEvVal;
        }
        else
        {
            assignment = (double)-solution.s / solution.f;
        }
        for (ll x : comp)
        {
            put[x] = assignment * function[x].f + function[x].s;
        }
    }
    cout << "YES\n";
    for (double x : put) cout << fixed << setprecision(6) << x << " ";
    cout << "\n";
    return 0;
}

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