제출 #1290223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290223		mhn_neek	Graph (BOI20_graph)	C++20	5 / 100	3 ms	348 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;
// ve Ver;
ld val[N],sum = 0;
ve Ver;

void dfs(lli v,ld X){
    vis[v] = 1;
    Ver.PB(v);
    val[v] = (ld)z[v]*X + f[v];
    // debug(val[v]);
    sum += abs(val[v]);
    for(auto [u,w] : adj[v]){
        if(vis[u] == 1){
            if(val[v] + val[u] != w){
                sum = INF;
            }
            continue;
        }
        z[u] = -z[v];
        f[u] = w-f[v];
        dfs(u,X);
    }
}


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));
    }
    ld ans = 0;
    FORS(i,n){
        if(vis[i] == 0){
            ld s=0,D= INF;
            for(ld l =  -2; l < 3; l += 0.5){
                sum = 0;
                z[i] = 1;
                f[i] = 0;
                for(auto u : Ver)vis[u] = 0;
                Ver.clear();
                dfs(i,l);
                D = min(D,sum);
                if(D == sum)s = l;
            }
            
            ans += D;
            // debug(s);
            for(auto u : Ver){
                val[u] = (ld)(z[u]*s + f[u]);
            }


            if(D == INF){
                cout<<"NO"<<endl;
                return 0;
            }

        }
    }  
    
    if(ans == INF){
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    FORS(i,n){
        cout<<val[i]<<sep;
    }

}

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