Submission #1170962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170962		alir3za_zar3	Graph (BOI20_graph)	C++20	0 / 100	69 ms	133448 KiB

Graph

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define     ld      long double 

const int mxN = 2e5+7;
const ld  vaL = 1e9+7 , inF = 2e18+7;
int n,m,typ; ld val[45][mxN];
bool vis[mxN];
vector<pair<int,ld>> e[mxN];
vector<int> vr;

void dfs (int v , int p , ld q)
{
    vr.push_back(v);
    val[typ][v] = q;
    vis[v] = true;
    for (auto [to,w] : e[v])
    {
        if (!vis[to]) dfs(to , v , w-q);
        else 
        {
            if (val[typ][to] != w-q)
                val[typ][to] = inF;
        }
    }
}

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
        
    cin >> n >> m; 
    for (int i=0; i<m; i++)
    {
        int u , v; ld w;
        cin >> u >> v >> w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    int out = 10; ld update = inF;
    for (int t=0; t<41; t++)
        fill_n(val[t] , mxN , vaL);
    for (int st=1; st<=n; st++)
    {
        if (vis[st]) continue;
        typ = 0;
        for (ld q=-10.0; q<=10.0; q+=0.5 , typ++)
        {
            dfs (st , st , q);
            for (auto v : vr)
                vis[v] = false;
        }
        typ = 41; dfs(st , st , 0);
    }
    for (int t=0; t<41; t++)
    {
        ld S = 0; bool mrk = 1;
        for (int i=1; i<=n; i++)
        {
            if (val[t][i] == inF)
            {
                mrk = false; break;
            }
            S += (val[t][i]<0 ? -1:1) * val[t][i];
        }
        if (mrk and S < update)
            update = S , out = t;
    }
    if (out == 10) cout << "NO\n";
    else 
    {
        cout << "YES\n";
        cout.precision(1);
        for (int i=1; i<=n; i++)
            cout << fixed << val[out][i] << ' ';
    }
} 

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