oj.uz

Submission #411541

# Submission time Handle Problem Language Result Execution time Memory
411541 2021-05-25T13:27:33 Z Ruxandra985 Graph (BOI20_graph) C++14
100 / 100
 199 ms 14404 KB 
#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 = -100 ; i <= 100 ; 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

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.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 2588 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 3 ms 2636 KB answer = YES
14 Correct 2 ms 2560 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 2 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO

Subtask #2
12.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 2588 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 3 ms 2636 KB answer = YES
14 Correct 2 ms 2560 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 2 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 2 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 3 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES

Subtask #3
17.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 2588 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 3 ms 2636 KB answer = YES
14 Correct 2 ms 2560 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 2 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 2 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 3 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2636 KB answer = YES
41 Correct 3 ms 2636 KB answer = NO
42 Correct 3 ms 2636 KB answer = YES
43 Correct 4 ms 2636 KB answer = YES
44 Correct 4 ms 2636 KB answer = YES
45 Correct 3 ms 2636 KB answer = YES
46 Correct 3 ms 2700 KB answer = YES
47 Correct 3 ms 2636 KB answer = YES
48 Correct 3 ms 2636 KB answer = YES

Subtask #4
24.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 2588 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 3 ms 2636 KB answer = YES
14 Correct 2 ms 2560 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 2 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 2 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 3 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2636 KB answer = YES
41 Correct 3 ms 2636 KB answer = NO
42 Correct 3 ms 2636 KB answer = YES
43 Correct 4 ms 2636 KB answer = YES
44 Correct 4 ms 2636 KB answer = YES
45 Correct 3 ms 2636 KB answer = YES
46 Correct 3 ms 2700 KB answer = YES
47 Correct 3 ms 2636 KB answer = YES
48 Correct 3 ms 2636 KB answer = YES
49 Correct 16 ms 3404 KB answer = YES
50 Correct 11 ms 3224 KB answer = YES
51 Correct 17 ms 3276 KB answer = YES
52 Correct 6 ms 3020 KB answer = NO
53 Correct 4 ms 2728 KB answer = YES
54 Correct 5 ms 2764 KB answer = YES
55 Correct 11 ms 3020 KB answer = YES
56 Correct 15 ms 3372 KB answer = YES
57 Correct 15 ms 3288 KB answer = YES
58 Correct 15 ms 3200 KB answer = YES
59 Correct 16 ms 3148 KB answer = YES
60 Correct 15 ms 3276 KB answer = YES
61 Correct 7 ms 3004 KB answer = YES
62 Correct 99 ms 7488 KB answer = NO
63 Correct 76 ms 7520 KB answer = YES
64 Correct 77 ms 7496 KB answer = NO
65 Correct 77 ms 7464 KB answer = YES
66 Correct 4 ms 2764 KB answer = YES

Subtask #5
42.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 2588 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 3 ms 2636 KB answer = YES
14 Correct 2 ms 2560 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 2 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 2 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 3 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2636 KB answer = YES
41 Correct 3 ms 2636 KB answer = NO
42 Correct 3 ms 2636 KB answer = YES
43 Correct 4 ms 2636 KB answer = YES
44 Correct 4 ms 2636 KB answer = YES
45 Correct 3 ms 2636 KB answer = YES
46 Correct 3 ms 2700 KB answer = YES
47 Correct 3 ms 2636 KB answer = YES
48 Correct 3 ms 2636 KB answer = YES
49 Correct 16 ms 3404 KB answer = YES
50 Correct 11 ms 3224 KB answer = YES
51 Correct 17 ms 3276 KB answer = YES
52 Correct 6 ms 3020 KB answer = NO
53 Correct 4 ms 2728 KB answer = YES
54 Correct 5 ms 2764 KB answer = YES
55 Correct 11 ms 3020 KB answer = YES
56 Correct 15 ms 3372 KB answer = YES
57 Correct 15 ms 3288 KB answer = YES
58 Correct 15 ms 3200 KB answer = YES
59 Correct 16 ms 3148 KB answer = YES
60 Correct 15 ms 3276 KB answer = YES
61 Correct 7 ms 3004 KB answer = YES
62 Correct 99 ms 7488 KB answer = NO
63 Correct 76 ms 7520 KB answer = YES
64 Correct 77 ms 7496 KB answer = NO
65 Correct 77 ms 7464 KB answer = YES
66 Correct 4 ms 2764 KB answer = YES
67 Correct 130 ms 8924 KB answer = YES
68 Correct 123 ms 10160 KB answer = YES
69 Correct 93 ms 10140 KB answer = YES
70 Correct 136 ms 12964 KB answer = YES
71 Correct 115 ms 10388 KB answer = YES
72 Correct 180 ms 10812 KB answer = YES
73 Correct 120 ms 10676 KB answer = YES
74 Correct 71 ms 7492 KB answer = YES
75 Correct 31 ms 6628 KB answer = NO
76 Correct 20 ms 3660 KB answer = YES
77 Correct 42 ms 4684 KB answer = YES
78 Correct 68 ms 6208 KB answer = YES
79 Correct 155 ms 9600 KB answer = YES
80 Correct 123 ms 7620 KB answer = YES
81 Correct 47 ms 8408 KB answer = NO
82 Correct 117 ms 10348 KB answer = YES
83 Correct 139 ms 10320 KB answer = YES
84 Correct 199 ms 10252 KB answer = YES
85 Correct 130 ms 10304 KB answer = YES
86 Correct 98 ms 10244 KB answer = YES
87 Correct 81 ms 9712 KB answer = NO
88 Correct 158 ms 10268 KB answer = YES
89 Correct 110 ms 9712 KB answer = YES
90 Correct 110 ms 9704 KB answer = YES
91 Correct 121 ms 9728 KB answer = YES
92 Correct 55 ms 6816 KB answer = YES
93 Correct 54 ms 6628 KB answer = YES
94 Correct 70 ms 8824 KB answer = NO
95 Correct 54 ms 9372 KB answer = NO
96 Correct 198 ms 14404 KB answer = YES
97 Correct 65 ms 8704 KB answer = NO