oj.uz

Submission #1101926

# Submission time Handle Problem Language Result Execution time Memory
1101926 2024-10-17T07:48:47 Z yoav_s Graph (BOI20_graph) C++17
0 / 100
 1 ms 504 KB 
#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;

#define double long double

struct Fraction
{
    ll nom, denom;
    Fraction(ll a, ll b)
    {
        nom = a; denom = b;
        ll g = gcd(nom, denom);
        nom /= g; denom /= g;
    }
    Fraction(p x)
    {
        nom = -x.s;
        denom = x.f;
        ll g = gcd(nom, denom);
        nom /= g; denom /= g;
    }

    Fraction operator+(Fraction &other)
    {
        return Fraction(nom * other.denom + other.nom * denom, denom * other.denom);
    }

    Fraction operator-(Fraction &other)
    {
        return Fraction(nom * other.denom - other.nom * denom, denom * other.denom);
    }

    Fraction operator*(ll a)
    {
        return Fraction(nom * a, denom);
    }
};

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));
                }
            }
            sort(all(events));
            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(10) << x << " ";
    cout << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Incorrect 1 ms 336 KB participant answer is larger than the answer of jury
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Incorrect 1 ms 336 KB participant answer is larger than the answer of jury
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Incorrect 1 ms 336 KB participant answer is larger than the answer of jury
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Incorrect 1 ms 336 KB participant answer is larger than the answer of jury
4 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Incorrect 1 ms 336 KB participant answer is larger than the answer of jury
4 Halted 0 ms 0 KB -