Submission #1290211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290211		mhn_neek	Graph (BOI20_graph)	C++20	0 / 100	3 ms	344 KiB

Graph

//In the name of God
#include<bits/stdc++.h>
/*MHN*/
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=3e5+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
#define SZ(X) (lli)X.size()
lli tmp;
lli n,m;
lli z[N],f[N];
bool vis[N];
vp adj[N];
vector<pair<pii,lli>> E;


void dfs(lli v){
    vis[v] = 1;
    for(auto [u,w] : adj[v]){
        if(vis[u] == 1)continue;
        z[u] = -z[v];
        f[u] = w-f[v];
        dfs(u);
    }
}

ld val[N];

ld check(ld x){
    FORS(i,n){
        val[i] = z[i]*x + f[i];
    }
    ld ans = 0;
    FORS(i,n)ans += abs(val[i]);
    for(auto i : E){
        lli a = i.fi.fi,b =i.fi.se,c =i.se;
        if(val[a] + val[b] != c)return INF;
    }
    return ans;
}

int main(){
    migmig;
    cin>>n>>m;
    FORS(i,m){
        lli a,b,c;
        cin>>a>>b>>c;
        E.PB(MP(MP(a,b),c));
        adj[a].PB(MP(b,c));
        adj[b].PB(MP(a,c));
    }
    FORS(i,n){
        if(vis[i] == 0){
            z[i] = 1;
            dfs(i);
        }
    }  
    ld s=0;
    ld ans=INF;
    for(ld i =  -100; i < 100; i += 0.5){
        ld x = check(i);
        ans = min(ans,x);
        if(ans == x)s = i;
    }
    if(ans == INF){
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    FORS(i,n){
        cout<<(ld)(z[i]*s + f[i])<<sep;
    }

}

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