Submission #1256281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256281		Jovica	Graph (BOI20_graph)	C++20	34 / 100	908 ms	7492 KiB

Graph

#include <bits/stdc++.h>

using namespace std;
int const maxn = 1e5+1;
vector<int> ans;
vector<vector<array<int,2> > > adj(maxn);
int gazda[maxn],vred[maxn][2],k;
bool visited[maxn];
int niza[maxn];

void bfs(int g,int k)
{
    int z = 0;
    queue<array<int,2> > q;queue<int> zima;
    q.push({g,k});
    while (q.size())
    {
        int p = q.front()[0],x = q.front()[1];gazda[p] = g;
        q.pop();
        zima.push(p);

        for (auto a: adj[p]){
            if (visited[a[0]]){
                if (vred[a[0]][0] + x != a[1]*2) z = -1e9;
                continue;
            }
            visited[a[0]] = true;vred[a[0]][0] = a[1]*2 - x; z+= abs(vred[a[0]][0]);
            q.push({a[0],vred[a[0]][0]});
        }
    }

    if (z<niza[g] && z>= 0){
        niza[g] = z;
        while (zima.size())
        {
            int p = zima.front();
            zima.pop();
            vred[p][1] = vred[p][0];
        }
    }
}

int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;for (int i=0;i<=n;i++) niza[i] = 1e9;
    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    for (k=0;k<=1000;k++)
    {
        memset(visited,0,sizeof(visited));
        for (int i=1;i<=n;i++)
            if (visited[i] == false) bfs(i,-500 + k);
    }

    for (int i=1;i<=n;i++)
        if (niza[gazda[i]] == 1e9) {
            cout<<"NO\n";
            return 0;
        }

    cout<<"YES\n";
    for (int i=1;i<=n;i++)
    {
        double d = vred[i][1];
        cout<<d/2<<" ";
    }

    return 0;
}

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