제출 #1289326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289326		djawadmain	Graph (BOI20_graph)	C++20	100 / 100	88 ms	21112 KiB

Graph

#include<iostream>
#include<vector>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0));
#define DECIMAL_OUTPUT cout << setprecision(9);
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define maxn 100001

pii st[maxn];
vector<int> uv;

vector<int> g2[maxn], g4[maxn];

bool seen[maxn];

int val[maxn];

void dfs(int v, int a, int b){

    seen[v] = true;
    st[v] = {a, b};
    uv.pb(v);

    for (int u: g2[v]) if (not seen[u]) dfs(u, -a, 2 - b);
    for (int u: g4[v]) if (not seen[u]) dfs(u, -a, 4 - b);

}

ll check(int mid){

    ll ans = 0;

    for (int u: uv) ans += abs(mid * st[u].ff + st[u].ss);

    return ans;
}

void SC(int rt){

    uv.clear();

    dfs(rt, 1, 0);

    int vs = -1, z = -1, k = -1;

    for (int v: uv){

        for (int u: g2[v]){

            if ((st[u].ff != st[v].ff * -1) or (st[u].ss + st[v].ss != 2)){

                vs = u;
                z = st[v].ff * -1;
                k = 2 - st[v].ss;
            }
        }

        for (int u: g4[v]){

            if ((st[u].ff != st[v].ff * -1) or (st[u].ss + st[v].ss != 4)){

                vs = u;
                z = st[v].ff * -1;
                k = 4 - st[v].ss;
            }
        }
    }

    int l = -1e6, r = 1e6;

    if (vs != -1){

        int nx = k - st[vs].ss;

        if (z == st[vs].ff) return;

        nx /= (st[vs].ff - z);

        l = nx;
        r = nx;
    }

    

    while (l < r){

        int m1 = (l + r) >> 1;
        int m2 = m1 + 1;

        ll r1 = check(m1);
        ll r2 = check(m2);

        if (r1 <= r2) r = m2 - 1;
        else l = m1 + 1;
    }

    for (int u: uv) val[u] = (l * st[u].ff + st[u].ss);
}

int n, m, ui, vi, ti;

int main(){

    RUN_LIKE_DJAWAD
    DECIMAL_OUTPUT

    cin >> n >> m;

    while (m--){

        cin >> ui >> vi >> ti;

        if (ti == 1){

            g2[ui].pb(vi);
            g2[vi].pb(ui);

        } else {

            g4[ui].pb(vi);
            g4[vi].pb(ui);
        }
    }

    for (int i = 1; i <= n; i++) if (not seen[i]) SC(i);

    bool ok = true;

    for (int i = 1; i <= n; i++){

        for (int u: g2[i]) if (val[i] + val[u] != 2) ok = false;
        for (int u: g4[i]) if (val[i] + val[u] != 4) ok = false;
    }

    if (not ok){

        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";

    for (int i = 1; i <= n; i++){

        ld vv = val[i];
        cout << vv / 2 << " ";
    }

    cout << "\n";
}

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