Submission #414577

#	Time	Username	Problem	Language	Result	Execution time	Memory
414577		nicolaalexandra	Graph (BOI20_graph)	C++14	100 / 100	548 ms	50624 KiB

Graph

#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
using namespace std;

pair <double,double> v[DIM];
vector <pair<int,int> > L[DIM];
vector <int> s,d,w;
int mrk[DIM];
map <pair<int,int>,int> f;

struct muchie{
    int x,y,cost;
} mch[DIM];

double x;
int cnt,nod_special,ok;
int n,m,i,j,xx,y,c;

void dfs (int nod){
    if (ok)
        return;
    mrk[nod] = 1;
    s.push_back(nod);
    w.push_back(nod);
    for (auto it : L[nod]){
        int vecin = it.first, val = it.second;

        if (v[vecin].first == INF){ /// nu am mai ajuns aici
            v[vecin] = make_pair(-v[nod].first,-v[nod].second + val);
        } else {
            if (v[vecin].first == -v[nod].first && v[vecin].second != -v[nod].second + val){
                /// nu am solutie
                ok = 1;
                return;
            }

            if (v[vecin].first != -v[nod].first){ /// inseamna ca aflu x ul
                x = 1.0*(val - v[vecin].second - v[nod].second) / (v[nod].first + v[vecin].first);
                /// acum trb sa refac (a,b) ale nodurilor deja procesate
                s.push_back(vecin);
                while (!s.empty()){
                    int idx = s.back();
                    double val2 = v[idx].first * x + v[idx].second;
                    v[idx] = make_pair(0,val2);

                    s.pop_back();
                }
            }
        }

        if (!mrk[vecin])
            dfs (vecin);
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    ok = 0;
    for (i=1;i<=m;i++){
        cin>>xx>>y>>c;
        L[xx].push_back(make_pair(y,c));
        L[y].push_back(make_pair(xx,c));

        if (xx > y)
            swap (xx,y);
        if (!f[make_pair(xx,y)])
            f[make_pair(xx,y)] = c;
        else {
            if (f[make_pair(xx,y)] != c)
                ok = 1;
        }

        mch[i] = {xx,y,c};
    }

    if (ok){
        cout<<"NO";
        return 0;
    }

    for (i=1;i<=n;i++){
        //sol[i] = INF;
        v[i] = make_pair(INF,INF);
        /// valoarea din fiecare nod o sa fie de forma a*x + b

        if (f[make_pair(i,i)])
            v[i] = make_pair(0,1.0 * f[make_pair(i,i)] / 2.0);
    }

    for (i=1;i<=n;i++){
        if (mrk[i])
            continue;

        v[i] = make_pair(1,0);
        x = INF, ok = 0;
        w.clear();
        dfs (i);

        if (ok){
            cout<<"NO";
            return 0;
        }

        if (w.size() == 1){
            v[i].first = 0;
            continue;
        }

        if (x == INF){
            /// inseamna ca am mai multe solutii
            d.clear();
            for (auto it : w){
                if (v[it].first < 0)
                    d.push_back(v[it].second);
                else d.push_back(-v[it].second);
            }
            sort (d.begin(),d.end());
            x = d[(d.size()-1)/2];

            for (auto it : w){
                double val = v[it].first * x + v[it].second;
                v[it] = make_pair(0,val);
            }
        }

    }

    /// mai verific odata conditiile
    ok = 0;
    for (i=1;i<=m;i++){
        int x = mch[i].x, y = mch[i].y;
        if (v[x].second + v[y].second != mch[i].cost){
            ok = 1;
            break;
        }}

    if (ok)
        cout<<"NO";
    else{
        cout<<"YES\n";
        for (i=1;i<=n;i++)
            cout<<v[i].second<<" ";
    }

    return 0;
}

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