Submission #1172342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172342		Vovamatrix	Graph (BOI20_graph)	C++20	0 / 100	1 ms	2632 KiB

Graph

//https://codeforces.com/contest/1387/problem/A
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 100007
#define MAXM 200007
vector<pll> adj[MAXN];
vector<double> tmp;
map<pll,ll> mm1,mm2;
ll n,m,a[MAXM],b[MAXM],c[MAXM];
double val[MAXN],x;
bool vis[MAXN],vis1[MAXN],checkx;
struct Line
{
    double k,n;
    Line(){};
    Line(double kk,double nn) {k=kk; n=nn;}
    double val(double x) {return k*x+n;}
    Line operator -(Line l) {return Line(k-l.k,n-l.n);}
};
Line l[MAXN];
bool DFS(ll u)
{
    if(checkx) return true;
    vis[u]=true; tmp.pb(val[u]);
    for(auto vw:adj[u])
    {
        ll v=vw.fi,w=vw.sc;
        Line lv=Line(0,(double)w)-l[u];
        if(!vis[v])
        {
            l[v]=lv;
            return DFS(v);
        }
        else if(l[v].k==lv.k && l[v].n!=lv.n) return false;
        else if(l[v].k!=lv.k) {x=(l[v].n-lv.n)/(lv.k-l[v].k); checkx=true; return true;}
    }
    return true;
}
void DFS1(ll u)
{
    vis1[u]=true;
    for(auto vw:adj[u])
    {
        ll v=vw.fi,w=vw.sc;
        if(vis1[v]) continue;
        val[v]=(double)w-val[u]; DFS1(v);
    }
}
bool Check()
{
    for(int i=1;i<=m;i++)
    {
        if(val[a[i]]+val[b[i]]!=(double)c[i]) return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        adj[a[i]].pb({b[i],c[i]}); adj[b[i]].pb({a[i],c[i]});
        if(a[i]>b[i]) swap(a[i],b[i]);
        if(c[i]==1) mm1[{a[i],b[i]}]++;
        else mm2[{a[i],b[i]}]++;
    }
    for(int i=1;i<=m;i++)
    {
        if(mm1[{a[i],b[i]}] && mm2[{a[i],b[i]}]) {cout<<"NO"<<endl; return 0;}
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis1[i])
        {
            if(adj[i].size()==0) val[i]=0;
            else
            {
                l[i]=Line(1,0); checkx=false; tmp.clear();
                if(!DFS(i)) {cout<<"NO"<<endl; return 0;}
                if(!checkx)
                {
                    sort(all(tmp));
                    x=tmp[(tmp.size()-1)/2];
                }
                val[i]=l[i].val(x); DFS1(i);
            }
        }
    }
    if(!Check()) {cout<<"NO"<<endl; return 0;}
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++) cout<<fixed<<setprecision(7)<<val[i]<<" ";
    return 0;
}

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