oj.uz

Submission #970937

# Submission time Handle Problem Language Result Execution time Memory
970937 2024-04-27T14:29:21 Z maxFedorchuk Graph (BOI20_graph) C++17
0 / 100
 2 ms 9052 KB 
#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].second);
        }
        sort(o.begin(),o.end());

        x=o[(o.size()-1)/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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -