Submission #411540

#	Time	Username	Problem	Language	Result	Execution time	Memory
411540		Ruxandra985	Graph (BOI20_graph)	C++14	58 / 100	103 ms	10280 KiB

Graph

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
double sol[DIMN];
int f[DIMN] , f2[DIMN];
vector <pair <int , int> > v[DIMN];
vector <int> taken;
pair <int , int> cod[DIMN];
deque <int> dq;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , i , a , y , z , found , nod , vecin , tip , mini , poz , sum;
    double x;
    fscanf (fin,"%d%d",&n,&m);
    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%d%d%d",&a,&y,&z);
        v[a].push_back(make_pair(y , z));
        v[y].push_back(make_pair(a , z));
    }

    for (int j = 1 ; j <= n ; j++){

        if (f2[j])
            continue;

        cod[j] = make_pair(0 , 1);
        dq.push_back(j);
        f[j] = 1;
        found = 0;

        taken.clear();

        while (!dq.empty() && !found){
            nod = dq.front();
            dq.pop_front();

            taken.push_back(nod);

            for (i = 0 ; i < v[nod].size() ; i++){
                vecin = v[nod][i].first;
                tip = v[nod][i].second;

                if (!f[vecin]){

                    dq.push_back(vecin);
                    f[vecin] = 1;

                    cod[vecin] = make_pair(tip - cod[nod].first , -cod[nod].second);

                }
                else {

                    /// momentul sa vezi daca relatiile sunt echivalente, contradictorii
                    /// sau daca sau solutia x

                    if (cod[vecin] == make_pair(tip - cod[nod].first , -cod[nod].second))
                        continue; /// echivalent

                    if (cod[vecin].second == -cod[nod].second && cod[vecin].first != tip - cod[nod].first){

                        fprintf (fout,"NO"); /// contradictorii
                        return 0;

                    }

                    if (cod[vecin].second != -cod[nod].second){

                        if (cod[vecin].second == 1){

                            x = 1.0 * (tip - cod[nod].first - cod[vecin].first) / 2;
                            found = 1;
                            break; /// ai aflat x

                        }
                        else {

                            x = 1.0 * (cod[vecin].first - tip + cod[nod].first) / 2;
                            found = 1;
                            break;

                        }

                    }

                }

            }

        }

        if (!found){

            mini = 2000000000;
            poz = -3;

            for (i = -20 ; i <= 20 ; i++){
                sum = 0;
                for (int k = 0 ; k < taken.size() ; k++){

                    nod = taken[k];

                    sum = sum + max(cod[nod].first + cod[nod].second * i , - (cod[nod].first + cod[nod].second * i ));

                }

                if (sum < mini){
                    mini = sum;
                    poz = i;
                }

            }

            x = poz;
            found = 1;
        }

        dq.clear();

        dq.push_back(j);
        f2[j] = 2;

        sol[j] = x;

        while (!dq.empty()){
            nod = dq.front();
            dq.pop_front();

            for (i = 0 ; i < v[nod].size() ; i++){
                vecin = v[nod][i].first;
                tip = v[nod][i].second;

                if (f2[vecin] != 2){

                    dq.push_back(vecin);
                    f2[vecin] = 2;

                    sol[vecin] = tip - sol[nod];

                }
                else {

                    if (sol[vecin] != tip - sol[nod]){
                        fprintf (fout,"NO");
                        return 0;
                    }

                }

            }
        }
    }

    cout << "YES\n";
    for (i = 1 ; i <= n ; i++){
        cout << sol[i] << " ";
    }

    return 0;
}

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:41:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (i = 0 ; i < v[nod].size() ; i++){
      |                          ~~^~~~~~~~~~~~~~~
Graph.cpp:100:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 for (int k = 0 ; k < taken.size() ; k++){
      |                                  ~~^~~~~~~~~~~~~~
Graph.cpp:130:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             for (i = 0 ; i < v[nod].size() ; i++){
      |                          ~~^~~~~~~~~~~~~~~
Graph.cpp:16:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     fscanf (fin,"%d%d",&n,&m);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
Graph.cpp:18:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         fscanf (fin,"%d%d%d",&a,&y,&z);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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