제출 #1308474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308474		Born_To_Laugh	Graph (BOI20_graph)	C++17	0 / 100	3 ms	4932 KiB

Graph

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 2e5 + 10;
const ld eps = 1e-8;

ld chosen = INF;

int n, m;
pair<int, int> func[maxn];
int vis[maxn];
vector<int> lis;
vector<pair<int,int>> adj[maxn];
map<pair<int, int>, int> freq;
pair<ld, ld> ans;
ld fires[maxn];

void dfs(int a){
    lis.push_back(a);
    vis[a] = 1;
    for(auto &edge: adj[a]){
        int elm = edge.fi;
        int wei = edge.se;
        if(!vis[elm]){
            func[elm].fi = -func[a].fi;
            func[elm].se = wei - func[a].se;
            freq[func[elm]]++;
            dfs(elm);
        }
        else{
            if(func[a].fi + func[elm].fi == 0){
                if(func[a].se + func[elm].se != wei){
                    cout << "NO\n";
                    exit(0);
                }
            }
            else{
                ld nxt = ((ld)wei - (ld)(func[a].se + func[elm].se)) / (func[a].fi + func[elm].fi);
                if(chosen == INF){
                    chosen = nxt;
                }
                else if(abs(chosen - nxt) > eps){
                    cout << "NO\n";
                    exit(0);
                }
            }
        }
    }
}
void solve(){
    cin >> n >> m;
    for(int i=1; i<=m; ++i){
        int a, b, c;cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for(int i=1; i<=n; ++i){
        if(vis[i])continue;
        lis.clear();
        func[i] = {1, 0};
        dfs(i);
        if(chosen != INF){
            ans.se = chosen;
        }
        else{
            vector<ld> tryy;
            for(auto &elm: freq){
                tryy.push_back((ld)-elm.fi.se / (ld)elm.fi.fi);
            }
            for(auto val: tryy){
                ld summ = 0;
                for(auto a: lis){
                    summ += func[a].fi * val + func[a].se;
                }
                ans = min(ans, make_pair(summ, val));
            }
        }
        for(auto a: lis){
            fires[a] = func[a].fi * ans.se + func[a].se;
        }
    }
    cout << "YES\n";
    for(int i=1; i<=n; ++i){
        cout << fires[i] << ' ';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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