Submission #970941

#	Time	Username	Problem	Language	Result	Execution time	Memory
970941		maxFedorchuk	Graph (BOI20_graph)	C++17	100 / 100	218 ms	37712 KiB

Graph

#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10,INF=1e18;

vector < pair < long long , long long > > mas[MX];
pair < long long , long double > cnt[MX];
long double ans[MX],vis[MX];

vector < long long > vr;

void DFS(long long zar)
{
    vis[zar]=1;
    vr.push_back(zar);

    for(auto [u,zn]:mas[zar])
    {
        if(!vis[u])
        {
            cnt[u]=make_pair(-cnt[zar].first,zn-cnt[zar].second);
            DFS(u);
        }
    }
}

void cntans()
{
    long double x=-INF,nwx;
    for(auto u:vr)
    {
        for(auto [a,b]:mas[u])
        {
            if(cnt[u].first==0 || cnt[u].first!=cnt[a].first)
            {
                if(cnt[u].second+cnt[a].second!=b)
                {
                    cout<<"NO\n";
                    exit(0);
                }
            }
            else
            {
                nwx=(b-cnt[u].second-cnt[a].second)/(2*cnt[u].first);

                if(x==-INF)
                {
                    x=nwx;
                }

                if(x!=nwx)
                {
                    cout<<"NO\n";
                    exit(0);
                }
            }
        }
    }

    if(x==-INF)
    {
        vector < long double > o;
        for(auto u:vr)
        {
            o.push_back(cnt[u].first*cnt[u].second*-1);
        }
        sort(o.begin(),o.end());

        x=o[o.size()/2];
    }

    for(auto u:vr)
    {
        ans[u]=cnt[u].first*x+cnt[u].second;
    }
}

void vip1(long long a,long long k)
{
    vr.clear();

    cnt[a]=make_pair(0,((k==1)?(0.5):1));
    DFS(a);

    cntans();
}

void vip2(long long a)
{
    vr.clear();

    cnt[a]=make_pair(1,0);
    DFS(a);

    cntans();
}

int main()
{
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);

    long long n,m;
    cin>>n>>m;

    fill(ans+1,ans+1+n,-INF);

    vector < pair < long long ,long long > > vc;
    for(long long i=1;i<=m;i++)
    {
        long long a,b,c;
        cin>>a>>b>>c;
        mas[a].push_back({b,c});
        mas[b].push_back({a,c});

        if(a==b)
        {
            vc.push_back({a,c});
        }
    }

    for(auto u:vc)
    {
        if(ans[u.first]==-INF)
        {
            vip1(u.first,u.second);
        }
    }

    for(long long i=1;i<=n;i++)
    {
        if(ans[i]==-INF)
        {
            vip2(i);
        }
    }

    cout<<"YES\n";
    for(long long i=1;i<=n;i++)
    {
        cout<<fixed<<setprecision(18)<<ans[i]<<" ";
    }
    cout<<"\n";

    return 0;
}

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