oj.uz

Submission #411500

# Submission time Handle Problem Language Result Execution time Memory
411500 2021-05-25T12:34:31 Z Ruxandra985 Graph (BOI20_graph) C++14
0 / 100
 2 ms 2636 KB 
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
double sol[DIMN];
int f[DIMN];
vector <pair <int , int> > v[DIMN];
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;
    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));
    }

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

    while (!dq.empty() && !found){
        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 (!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){
        x = 0;
        found = 1;
    }

    if (found){

        dq.clear();

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

        sol[1] = 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 (f[vecin] != 2){

                    dq.push_back(vecin);
                    f[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;

    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Incorrect 2 ms 2636 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Incorrect 2 ms 2636 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Incorrect 2 ms 2636 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Incorrect 2 ms 2636 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Incorrect 2 ms 2636 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -