Submission #932205

#	Time	Username	Problem	Language	Result	Execution time	Memory
932205		Faisal_Saqib	Graph (BOI20_graph)	C++17	0 / 100	1 ms	600 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
#define ld long double
vector<pair<int,int>> ma[N];
int h[N],pre[N];
bool vis[N];
vector<pair<int,ld>> pos;
set<int> anc;
double val[N],sum[N],fin[N];
bool flip[N],posa[N];
void dfs(int x,int p=-1)
{
    vis[x]=1;
    cout<<"Parent "<<p<<' '<<x<<endl;
    if(p==-1)
    {
        h[x]=0;
    }
    else{
        h[x]=(h[p]+1)%2;
    }
    vis[x]=1;
    anc.insert(x);
    for(auto [y,w]:ma[x])
    {
        if(y!=p)
        {
            if(vis[y] and anc.find(y)!=anc.end())
            {
                // Cylce
                // WE 
                // a[1]->a[2]->a[3]->a[4]
                //a[1]+a[2]==pre[2]
                // a[1]+a[2]+a[2]+a[3]=pre[3]
                // a[1]+a[2]+a[2]+a[3]+a[3]+a[4]=pre[4]
                // a[3]+a[4]=w
                // pre[4]-w
                cout<<"Hola Cycle "<<x<<' '<<y<<endl;
                if((h[y]==h[x]))
                {
                    if(h[x]==1)
                    {
                        ld p=pre[y]-pre[x];
                        ld q=w;
                        pos.push_back({y,(p+q)/2.0});
                    }
                    else{
                        ld p=pre[x];
                        ld q=w;
                        pos.push_back({y,(p+q)/2.0});
                    }
                }
            }
            else{
                if(h[x]==0)
                {
                    pre[y]=pre[x]+w;
                }
                else{
                    pre[y]=pre[x]-w;
                }
                dfs(y,x);
            }
        }
    }
    anc.erase(x);
}
set<int> visp;
bool check(int x,double vl)
{
    // cout<<"For vertex "<<x<<" then it is "<<vl<<endl;
    // visp.insert(x);
    vis[x]=1;
    flip[x]=1;
    val[x]=vl;
    for(auto [y,w]:ma[x])
    {
        // if(visp.find(y)==visp.end())
        if(!vis[y])
        {
            flip[x]&=check(y,w-vl);
        }
        else if((val[y])!=(w-val[x]))
        {
            flip[x]=0;
        }
        else
        {
            flip[x]&=flip[y];
        }
    }
    return flip[x];
}
int part[N];
void init(int n)
{
    for(int i=1;i<=n;i++)
        part[i]=i;
}
int root(int x)
{
    return ((part[x]==x)?x:part[x]=root(part[x]));
}
void join(int x,int y)
{
    x=root(x);
    y=root(y);
    if(x!=y)
    {
        part[x]=y;
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        sum[i]=1e9;
    }
    init(n);
    for(int j=0;j<m;j++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        join(a,b);
        ma[a].push_back({b,c});
        ma[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++)
    {    
        if(!posa[root(i)])
        {
            for(double vl=-3;vl<=3;vl+=0.5)
            {
                for(int i=1;i<=n;i++){
                    vis[i]=0;
                }
                if(check(i,vl))
                {
                    // cout<<"Can place values\n";
                    double dp=0;
                    for(auto j:visp)
                        dp+=abs(val[j]);
                    // cout<<"Done sum = "<<dp<<endl;
                    if(dp<sum[root(i)])
                    {
                        posa[root(i)]=1;
                        for(auto j:visp)
                            fin[j]=val[j];
                        sum[root(i)]=dp;
                    }
                }
            }
        }
    }
    bool pos=1;
    for(int i=1;i<=n;i++)
    {
        pos&=(posa[root(i)]);
    }
    if(pos)
    {
        cout<<"YES\n";
        for(int i=1;i<=n;i++)
        {
            cout<<fin[i]<<' ';
        }
        cout<<'\n';
    }
    else{
        cout<<"NO\n";
    }
    return 0;
}
/*

a[4]+a[1]
a[1]+a[2]
a[2]+a[3]


a[4]+a[3]
// a[3]-a[1]
// a[1]-a[3] == p
// a[1]+a[3] == q
// a[1] == (p+q)/2
*/

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