제출 #1290261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290261		mhn_neek	Graph (BOI20_graph)	C++20	58 / 100	151 ms	49404 KiB

Graph

//In the name of God
#include<bits/stdc++.h>
/*MHN*/
using namespace std;
typedef long long int lli;
typedef float ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=2e5+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,gooz;
// ve Ver;
ld val[N],sum = 0;
ve Ver;
const ld EPS = 1e-9L; 

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



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;
            z[i] = 1;
            f[i] = 0;
            dfs(i);
            ve w;
            for(auto u : Ver){
                    w.PB(z[u]*f[u]);
            }
            sort(all(w));
            lli med=w[SZ(w)/2];
            sum = 0;
            for(auto u : Ver){
                val[u] = (ld)z[u]*med + f[u];
                sum += fabsl(val[u]);
            }
            bool ok = 1;
            for(auto j : gooz){
                if(fabsl(val[j.fi.fi] + val[j.fi.se] - (ld)j.se) > EPS) ok = 0;
            }
            if(ok){
            D = min(D,sum);
            if(fabsl(D - sum) < EPS) s = med;
            }
            med=w[(SZ(w) == 1 ? SZ(w)/2 : SZ(w)/2  + 1)];
            sum = 0;
            for(auto u : Ver){
                val[u] = (ld)z[u]*med + f[u];
                sum += fabsl(val[u]);
            }
            ok = 1;
            for(auto j : gooz){
                if(fabsl(val[j.fi.fi] + val[j.fi.se] - (ld)j.se) > EPS) ok = 0;
            }
            if(ok){
            D = min(D,sum);
            if(fabsl(D - sum) < EPS) s = med;
            }
            
            for(ld l =  -30; l <= 30; l += 0.5){
                sum = 0;
                for(auto u : Ver){
                    val[u] = (ld)z[u]*l + f[u];
                    sum += fabsl(val[u]);
                }
                bool ok = 1;
                for(auto j : gooz){
                    if(fabsl(val[j.fi.fi] + val[j.fi.se] - (ld)j.se) > EPS) ok = 0;
                }
                if(!ok)continue;
                D = min(D,sum);
                if(fabsl(D - sum) < EPS) s = l;
            }

            ans += D;
            // debug(s);
            for(auto u : Ver){
                val[u] = (ld)(z[u]*s + f[u]);
            }
            Ver.clear();
            gooz.clear();

               if(D > (ld)INF/2){
                cout<<"NO"<<endl;
                return 0;
            }

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

}

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