oj.uz

Submission #1101927

# Submission time Handle Problem Language Result Execution time Memory
1101927 2024-10-17T07:49:46 Z yoav_s Graph (BOI20_graph) C++17
100 / 100
 140 ms 36772 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 1 ms 336 KB answer = NO
5 Correct 1 ms 336 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 1 ms 460 KB answer = YES
8 Correct 1 ms 340 KB answer = YES
9 Correct 1 ms 340 KB answer = NO
10 Correct 1 ms 340 KB answer = YES
11 Correct 1 ms 340 KB answer = YES
12 Correct 1 ms 340 KB answer = NO
13 Correct 1 ms 340 KB answer = YES
14 Correct 1 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 1 ms 340 KB answer = YES
18 Correct 1 ms 340 KB answer = YES
19 Correct 1 ms 340 KB answer = YES
20 Correct 1 ms 376 KB answer = YES
21 Correct 1 ms 340 KB answer = YES
22 Correct 1 ms 456 KB answer = NO
23 Correct 1 ms 340 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 1 ms 336 KB answer = NO
5 Correct 1 ms 336 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 1 ms 460 KB answer = YES
8 Correct 1 ms 340 KB answer = YES
9 Correct 1 ms 340 KB answer = NO
10 Correct 1 ms 340 KB answer = YES
11 Correct 1 ms 340 KB answer = YES
12 Correct 1 ms 340 KB answer = NO
13 Correct 1 ms 340 KB answer = YES
14 Correct 1 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 1 ms 340 KB answer = YES
18 Correct 1 ms 340 KB answer = YES
19 Correct 1 ms 340 KB answer = YES
20 Correct 1 ms 376 KB answer = YES
21 Correct 1 ms 340 KB answer = YES
22 Correct 1 ms 456 KB answer = NO
23 Correct 1 ms 340 KB answer = NO
24 Correct 1 ms 428 KB answer = YES
25 Correct 1 ms 592 KB answer = YES
26 Correct 1 ms 456 KB answer = YES
27 Correct 1 ms 340 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 340 KB answer = YES
30 Correct 1 ms 340 KB answer = NO
31 Correct 1 ms 340 KB answer = YES
32 Correct 1 ms 340 KB answer = YES
33 Correct 1 ms 340 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 340 KB answer = YES
36 Correct 1 ms 596 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 1 ms 336 KB answer = NO
5 Correct 1 ms 336 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 1 ms 460 KB answer = YES
8 Correct 1 ms 340 KB answer = YES
9 Correct 1 ms 340 KB answer = NO
10 Correct 1 ms 340 KB answer = YES
11 Correct 1 ms 340 KB answer = YES
12 Correct 1 ms 340 KB answer = NO
13 Correct 1 ms 340 KB answer = YES
14 Correct 1 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 1 ms 340 KB answer = YES
18 Correct 1 ms 340 KB answer = YES
19 Correct 1 ms 340 KB answer = YES
20 Correct 1 ms 376 KB answer = YES
21 Correct 1 ms 340 KB answer = YES
22 Correct 1 ms 456 KB answer = NO
23 Correct 1 ms 340 KB answer = NO
24 Correct 1 ms 428 KB answer = YES
25 Correct 1 ms 592 KB answer = YES
26 Correct 1 ms 456 KB answer = YES
27 Correct 1 ms 340 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 340 KB answer = YES
30 Correct 1 ms 340 KB answer = NO
31 Correct 1 ms 340 KB answer = YES
32 Correct 1 ms 340 KB answer = YES
33 Correct 1 ms 340 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 340 KB answer = YES
36 Correct 1 ms 596 KB answer = YES
37 Correct 1 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 1 ms 596 KB answer = YES
40 Correct 1 ms 596 KB answer = YES
41 Correct 1 ms 596 KB answer = NO
42 Correct 1 ms 596 KB answer = YES
43 Correct 2 ms 760 KB answer = YES
44 Correct 1 ms 596 KB answer = YES
45 Correct 1 ms 596 KB answer = YES
46 Correct 1 ms 340 KB answer = YES
47 Correct 1 ms 596 KB answer = YES
48 Correct 1 ms 596 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 1 ms 336 KB answer = NO
5 Correct 1 ms 336 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 1 ms 460 KB answer = YES
8 Correct 1 ms 340 KB answer = YES
9 Correct 1 ms 340 KB answer = NO
10 Correct 1 ms 340 KB answer = YES
11 Correct 1 ms 340 KB answer = YES
12 Correct 1 ms 340 KB answer = NO
13 Correct 1 ms 340 KB answer = YES
14 Correct 1 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 1 ms 340 KB answer = YES
18 Correct 1 ms 340 KB answer = YES
19 Correct 1 ms 340 KB answer = YES
20 Correct 1 ms 376 KB answer = YES
21 Correct 1 ms 340 KB answer = YES
22 Correct 1 ms 456 KB answer = NO
23 Correct 1 ms 340 KB answer = NO
24 Correct 1 ms 428 KB answer = YES
25 Correct 1 ms 592 KB answer = YES
26 Correct 1 ms 456 KB answer = YES
27 Correct 1 ms 340 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 340 KB answer = YES
30 Correct 1 ms 340 KB answer = NO
31 Correct 1 ms 340 KB answer = YES
32 Correct 1 ms 340 KB answer = YES
33 Correct 1 ms 340 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 340 KB answer = YES
36 Correct 1 ms 596 KB answer = YES
37 Correct 1 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 1 ms 596 KB answer = YES
40 Correct 1 ms 596 KB answer = YES
41 Correct 1 ms 596 KB answer = NO
42 Correct 1 ms 596 KB answer = YES
43 Correct 2 ms 760 KB answer = YES
44 Correct 1 ms 596 KB answer = YES
45 Correct 1 ms 596 KB answer = YES
46 Correct 1 ms 340 KB answer = YES
47 Correct 1 ms 596 KB answer = YES
48 Correct 1 ms 596 KB answer = YES
49 Correct 10 ms 2888 KB answer = YES
50 Correct 9 ms 2256 KB answer = YES
51 Correct 10 ms 2584 KB answer = YES
52 Correct 5 ms 2236 KB answer = NO
53 Correct 2 ms 596 KB answer = YES
54 Correct 3 ms 892 KB answer = YES
55 Correct 5 ms 1616 KB answer = YES
56 Correct 9 ms 2888 KB answer = YES
57 Correct 8 ms 1792 KB answer = YES
58 Correct 9 ms 2136 KB answer = YES
59 Correct 8 ms 1784 KB answer = YES
60 Correct 9 ms 2252 KB answer = YES
61 Correct 4 ms 1364 KB answer = YES
62 Correct 66 ms 30812 KB answer = NO
63 Correct 78 ms 30792 KB answer = YES
64 Correct 59 ms 30792 KB answer = NO
65 Correct 69 ms 30652 KB answer = YES
66 Correct 4 ms 596 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 1 ms 336 KB answer = NO
5 Correct 1 ms 336 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 1 ms 460 KB answer = YES
8 Correct 1 ms 340 KB answer = YES
9 Correct 1 ms 340 KB answer = NO
10 Correct 1 ms 340 KB answer = YES
11 Correct 1 ms 340 KB answer = YES
12 Correct 1 ms 340 KB answer = NO
13 Correct 1 ms 340 KB answer = YES
14 Correct 1 ms 340 KB answer = YES
15 Correct 1 ms 340 KB answer = YES
16 Correct 1 ms 340 KB answer = YES
17 Correct 1 ms 340 KB answer = YES
18 Correct 1 ms 340 KB answer = YES
19 Correct 1 ms 340 KB answer = YES
20 Correct 1 ms 376 KB answer = YES
21 Correct 1 ms 340 KB answer = YES
22 Correct 1 ms 456 KB answer = NO
23 Correct 1 ms 340 KB answer = NO
24 Correct 1 ms 428 KB answer = YES
25 Correct 1 ms 592 KB answer = YES
26 Correct 1 ms 456 KB answer = YES
27 Correct 1 ms 340 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 340 KB answer = YES
30 Correct 1 ms 340 KB answer = NO
31 Correct 1 ms 340 KB answer = YES
32 Correct 1 ms 340 KB answer = YES
33 Correct 1 ms 340 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 340 KB answer = YES
36 Correct 1 ms 596 KB answer = YES
37 Correct 1 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 1 ms 596 KB answer = YES
40 Correct 1 ms 596 KB answer = YES
41 Correct 1 ms 596 KB answer = NO
42 Correct 1 ms 596 KB answer = YES
43 Correct 2 ms 760 KB answer = YES
44 Correct 1 ms 596 KB answer = YES
45 Correct 1 ms 596 KB answer = YES
46 Correct 1 ms 340 KB answer = YES
47 Correct 1 ms 596 KB answer = YES
48 Correct 1 ms 596 KB answer = YES
49 Correct 10 ms 2888 KB answer = YES
50 Correct 9 ms 2256 KB answer = YES
51 Correct 10 ms 2584 KB answer = YES
52 Correct 5 ms 2236 KB answer = NO
53 Correct 2 ms 596 KB answer = YES
54 Correct 3 ms 892 KB answer = YES
55 Correct 5 ms 1616 KB answer = YES
56 Correct 9 ms 2888 KB answer = YES
57 Correct 8 ms 1792 KB answer = YES
58 Correct 9 ms 2136 KB answer = YES
59 Correct 8 ms 1784 KB answer = YES
60 Correct 9 ms 2252 KB answer = YES
61 Correct 4 ms 1364 KB answer = YES
62 Correct 66 ms 30812 KB answer = NO
63 Correct 78 ms 30792 KB answer = YES
64 Correct 59 ms 30792 KB answer = NO
65 Correct 69 ms 30652 KB answer = YES
66 Correct 4 ms 596 KB answer = YES
67 Correct 80 ms 26412 KB answer = YES
68 Correct 74 ms 26308 KB answer = YES
69 Correct 63 ms 17704 KB answer = YES
70 Correct 90 ms 36772 KB answer = YES
71 Correct 64 ms 17708 KB answer = YES
72 Correct 81 ms 23452 KB answer = YES
73 Correct 77 ms 18232 KB answer = YES
74 Correct 55 ms 11080 KB answer = YES
75 Correct 25 ms 11120 KB answer = NO
76 Correct 11 ms 3144 KB answer = YES
77 Correct 20 ms 5320 KB answer = YES
78 Correct 41 ms 10304 KB answer = YES
79 Correct 74 ms 21564 KB answer = YES
80 Correct 59 ms 14764 KB answer = YES
81 Correct 41 ms 21048 KB answer = NO
82 Correct 79 ms 19120 KB answer = YES
83 Correct 87 ms 19516 KB answer = YES
84 Correct 108 ms 26792 KB answer = YES
85 Correct 81 ms 22952 KB answer = YES
86 Correct 70 ms 17704 KB answer = YES
87 Correct 38 ms 14276 KB answer = NO
88 Correct 91 ms 15428 KB answer = YES
89 Correct 74 ms 13084 KB answer = YES
90 Correct 78 ms 13132 KB answer = YES
91 Correct 83 ms 13740 KB answer = YES
92 Correct 37 ms 8500 KB answer = YES
93 Correct 36 ms 8504 KB answer = YES
94 Correct 47 ms 19624 KB answer = NO
95 Correct 36 ms 12364 KB answer = NO
96 Correct 140 ms 36384 KB answer = YES
97 Correct 35 ms 17808 KB answer = NO