Submission #720746

#	Time	Username	Problem	Language	Result	Execution time	Memory
720746		n0sk1ll	Graph (BOI20_graph)	C++17	100 / 100	162 ms	22852 KiB

Graph

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const double eps=1e-9;

vector<pii> w1,w2;
vector<vector<pii>> g(100005); //(gde, boja)
int znak[100005],shift[100005]; //x - c, ili mozda x+c, takodje proverava posecenost ako znak[]=0
ld ans[100005];

bool determined=false; //da li x vec mora biti postavljeno jednacinama?
double x; //ako je determined, sta je ona?

vector<int> poseceni;
void dfs(int p)
{
    poseceni.pb(p);
    for (auto it : g[p])
    {
        if (znak[it.xx])
        {
            if (znak[it.xx]==znak[p]){
                //x + shift[p] + x + shift[it.xx] = it.yy
                double tx=(double)(it.yy-shift[p]-shift[it.xx])*znak[p]/2;
                if (determined){
                    if (abs(tx-x)>eps) cout<<"NO\n",exit(0);
                }
                else x=tx,determined=true;
            }
            else if (shift[p]+shift[it.xx]!=it.yy)
            {

                cout<<"NO\n",exit(0);
            }
        }
        else
        {
            znak[it.xx]=-znak[p];
            shift[it.xx]=it.yy-shift[p];
            dfs(it.xx);
        }
    }
}

void solve(int root)
{
    poseceni.clear();
    determined=false;
    znak[root]=1,dfs(root);

    if (!determined)
    {
        vector<int> smene;
        for (auto i : poseceni) smene.pb(-znak[i]*shift[i]);
        sort(all(smene));
        int n=(int)smene.size();
        x=smene[n/2];
    }

    for (auto it : poseceni) ans[it]=shift[it]+znak[it]*x;
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    while (m--)
    {
        int u,v,w; cin>>u>>v>>w;
        g[u].pb({v,w}),g[v].pb({u,w});
        if (w==1) w1.pb({u,v});
        else w2.pb({u,v});
    }

    fff(i,1,n) if (!znak[i]) solve(i);

    cout<<"YES\n";
    fff(i,1,n) cout<<ans[i]<<" ";
}

//Note to self: Check for overflow

/*

7 12 2
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 3 2
3 4 2
4 5 2
5 6 2
6 7 2
7 2 2

8 10
2 7 1
7 8 1
8 6 1
2 3 2
3 6 2
1 2 2
5 6 2
4 3 1
1 4 1
4 5 1

*/

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