Submission

PPPPPPP---

Score: 70

User: Nagorn

Problemset: สมดุลย์

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-05 13:16:14

#include <bits/stdc++.h>
#define int long long
#define pii pair <int,int>
#define tiii tuple <int, int, int>
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e18;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int32_t main(){
    iShowSpeed;
    int n;
    cin >> n;
    vector <pii> adj(n + 1);
    vector <double> weight(n + 1);
    vector <pii> link(n + 1);
    vector <pair <bool, bool>> single(n + 1);
    for (int i = 1; i <= n; i++) {
        int a, l, b, r;
        cin >> a >> l >> b >> r;
        if (!a) {
            adj[i].f = l;
            link[l] = {i, 0};
        }
        else {
            single[i].f = true;
            adj[i].f = l;
        }
        if (!b) {
            adj[i].s = r;
            link[r] = {i, 1};
        }
        else {
            adj[i].s = r;
            single[i].s = true;
        }
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": \n";
    //     cout << "connect: " << adj[i].f << ' ' << adj[i].s << "\n";
    //     cout << "single or not: " << (single[i].f && single[i].s) << '\n';
    //     cout << "link: " << link[i].f << ' ' << link[i].s << '\n';
    // }
    double sum = 0;
    int rou = 1;
    vector <bool> visited(n + 1);
    while (1) {
        // cout << "Round " << rou << ": \n";
        for (int i = 1; i <= n; i++) {
            if (single[i].f && single[i].s && !visited[i]) {
                visited[i] = true;
                // cout << i << ": ";
                if (adj[i].f != adj[i].s) {
                    double dif = abs(adj[i].f - adj[i].s);
                    // cout << dif;
                    sum += dif;
                }
                auto [u, di] = link[i];
                if (di) {
                    adj[u].s = max(adj[i].f, adj[i].s) * 2;
                    single[u].s = true;
                }
                else {
                    adj[u].f = max(adj[i].f, adj[i].s) * 2;
                    single[u].f = true;
                }
                // cout << "\n";
                if (i == 1) {
                    cout << sum;
                    return 0;
                }
            }
        }
        rou++;
    }
    // cout << sum;
}