oj.uz

Submission #414577

# Submission time Handle Problem Language Result Execution time Memory
414577 2021-05-30T16:47:54 Z nicolaalexandra Graph (BOI20_graph) C++14
100 / 100
 548 ms 50624 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB answer = YES
2 Correct 4 ms 4992 KB answer = YES
3 Correct 4 ms 4940 KB answer = YES
4 Correct 4 ms 4940 KB answer = NO
5 Correct 4 ms 5008 KB answer = YES
6 Correct 4 ms 4940 KB answer = YES
7 Correct 5 ms 5000 KB answer = YES
8 Correct 4 ms 4940 KB answer = YES
9 Correct 4 ms 4940 KB answer = NO
10 Correct 4 ms 4940 KB answer = YES
11 Correct 4 ms 4940 KB answer = YES
12 Correct 4 ms 4940 KB answer = NO
13 Correct 4 ms 4940 KB answer = YES
14 Correct 4 ms 4940 KB answer = YES
15 Correct 4 ms 5012 KB answer = YES
16 Correct 4 ms 4940 KB answer = YES
17 Correct 4 ms 4940 KB answer = YES
18 Correct 4 ms 4940 KB answer = YES
19 Correct 4 ms 5012 KB answer = YES
20 Correct 4 ms 4984 KB answer = YES
21 Correct 4 ms 4940 KB answer = YES
22 Correct 4 ms 5008 KB answer = NO
23 Correct 4 ms 5008 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB answer = YES
2 Correct 4 ms 4992 KB answer = YES
3 Correct 4 ms 4940 KB answer = YES
4 Correct 4 ms 4940 KB answer = NO
5 Correct 4 ms 5008 KB answer = YES
6 Correct 4 ms 4940 KB answer = YES
7 Correct 5 ms 5000 KB answer = YES
8 Correct 4 ms 4940 KB answer = YES
9 Correct 4 ms 4940 KB answer = NO
10 Correct 4 ms 4940 KB answer = YES
11 Correct 4 ms 4940 KB answer = YES
12 Correct 4 ms 4940 KB answer = NO
13 Correct 4 ms 4940 KB answer = YES
14 Correct 4 ms 4940 KB answer = YES
15 Correct 4 ms 5012 KB answer = YES
16 Correct 4 ms 4940 KB answer = YES
17 Correct 4 ms 4940 KB answer = YES
18 Correct 4 ms 4940 KB answer = YES
19 Correct 4 ms 5012 KB answer = YES
20 Correct 4 ms 4984 KB answer = YES
21 Correct 4 ms 4940 KB answer = YES
22 Correct 4 ms 5008 KB answer = NO
23 Correct 4 ms 5008 KB answer = NO
24 Correct 4 ms 4940 KB answer = YES
25 Correct 4 ms 5012 KB answer = YES
26 Correct 4 ms 4940 KB answer = YES
27 Correct 4 ms 4940 KB answer = YES
28 Correct 4 ms 4940 KB answer = YES
29 Correct 4 ms 4940 KB answer = YES
30 Correct 4 ms 4940 KB answer = NO
31 Correct 4 ms 4940 KB answer = YES
32 Correct 4 ms 4976 KB answer = YES
33 Correct 4 ms 5004 KB answer = YES
34 Correct 4 ms 4940 KB answer = YES
35 Correct 4 ms 4940 KB answer = YES
36 Correct 4 ms 4940 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB answer = YES
2 Correct 4 ms 4992 KB answer = YES
3 Correct 4 ms 4940 KB answer = YES
4 Correct 4 ms 4940 KB answer = NO
5 Correct 4 ms 5008 KB answer = YES
6 Correct 4 ms 4940 KB answer = YES
7 Correct 5 ms 5000 KB answer = YES
8 Correct 4 ms 4940 KB answer = YES
9 Correct 4 ms 4940 KB answer = NO
10 Correct 4 ms 4940 KB answer = YES
11 Correct 4 ms 4940 KB answer = YES
12 Correct 4 ms 4940 KB answer = NO
13 Correct 4 ms 4940 KB answer = YES
14 Correct 4 ms 4940 KB answer = YES
15 Correct 4 ms 5012 KB answer = YES
16 Correct 4 ms 4940 KB answer = YES
17 Correct 4 ms 4940 KB answer = YES
18 Correct 4 ms 4940 KB answer = YES
19 Correct 4 ms 5012 KB answer = YES
20 Correct 4 ms 4984 KB answer = YES
21 Correct 4 ms 4940 KB answer = YES
22 Correct 4 ms 5008 KB answer = NO
23 Correct 4 ms 5008 KB answer = NO
24 Correct 4 ms 4940 KB answer = YES
25 Correct 4 ms 5012 KB answer = YES
26 Correct 4 ms 4940 KB answer = YES
27 Correct 4 ms 4940 KB answer = YES
28 Correct 4 ms 4940 KB answer = YES
29 Correct 4 ms 4940 KB answer = YES
30 Correct 4 ms 4940 KB answer = NO
31 Correct 4 ms 4940 KB answer = YES
32 Correct 4 ms 4976 KB answer = YES
33 Correct 4 ms 5004 KB answer = YES
34 Correct 4 ms 4940 KB answer = YES
35 Correct 4 ms 4940 KB answer = YES
36 Correct 4 ms 4940 KB answer = YES
37 Correct 4 ms 4940 KB answer = YES
38 Correct 5 ms 4940 KB answer = YES
39 Correct 5 ms 5136 KB answer = YES
40 Correct 6 ms 5196 KB answer = YES
41 Correct 6 ms 5144 KB answer = NO
42 Correct 6 ms 5196 KB answer = YES
43 Correct 6 ms 5196 KB answer = YES
44 Correct 6 ms 5196 KB answer = YES
45 Correct 6 ms 5148 KB answer = YES
46 Correct 5 ms 5068 KB answer = YES
47 Correct 6 ms 5196 KB answer = YES
48 Correct 6 ms 5196 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB answer = YES
2 Correct 4 ms 4992 KB answer = YES
3 Correct 4 ms 4940 KB answer = YES
4 Correct 4 ms 4940 KB answer = NO
5 Correct 4 ms 5008 KB answer = YES
6 Correct 4 ms 4940 KB answer = YES
7 Correct 5 ms 5000 KB answer = YES
8 Correct 4 ms 4940 KB answer = YES
9 Correct 4 ms 4940 KB answer = NO
10 Correct 4 ms 4940 KB answer = YES
11 Correct 4 ms 4940 KB answer = YES
12 Correct 4 ms 4940 KB answer = NO
13 Correct 4 ms 4940 KB answer = YES
14 Correct 4 ms 4940 KB answer = YES
15 Correct 4 ms 5012 KB answer = YES
16 Correct 4 ms 4940 KB answer = YES
17 Correct 4 ms 4940 KB answer = YES
18 Correct 4 ms 4940 KB answer = YES
19 Correct 4 ms 5012 KB answer = YES
20 Correct 4 ms 4984 KB answer = YES
21 Correct 4 ms 4940 KB answer = YES
22 Correct 4 ms 5008 KB answer = NO
23 Correct 4 ms 5008 KB answer = NO
24 Correct 4 ms 4940 KB answer = YES
25 Correct 4 ms 5012 KB answer = YES
26 Correct 4 ms 4940 KB answer = YES
27 Correct 4 ms 4940 KB answer = YES
28 Correct 4 ms 4940 KB answer = YES
29 Correct 4 ms 4940 KB answer = YES
30 Correct 4 ms 4940 KB answer = NO
31 Correct 4 ms 4940 KB answer = YES
32 Correct 4 ms 4976 KB answer = YES
33 Correct 4 ms 5004 KB answer = YES
34 Correct 4 ms 4940 KB answer = YES
35 Correct 4 ms 4940 KB answer = YES
36 Correct 4 ms 4940 KB answer = YES
37 Correct 4 ms 4940 KB answer = YES
38 Correct 5 ms 4940 KB answer = YES
39 Correct 5 ms 5136 KB answer = YES
40 Correct 6 ms 5196 KB answer = YES
41 Correct 6 ms 5144 KB answer = NO
42 Correct 6 ms 5196 KB answer = YES
43 Correct 6 ms 5196 KB answer = YES
44 Correct 6 ms 5196 KB answer = YES
45 Correct 6 ms 5148 KB answer = YES
46 Correct 5 ms 5068 KB answer = YES
47 Correct 6 ms 5196 KB answer = YES
48 Correct 6 ms 5196 KB answer = YES
49 Correct 26 ms 7240 KB answer = YES
50 Correct 26 ms 7628 KB answer = YES
51 Correct 25 ms 7628 KB answer = YES
52 Correct 20 ms 7100 KB answer = NO
53 Correct 6 ms 5196 KB answer = YES
54 Correct 8 ms 5532 KB answer = YES
55 Correct 14 ms 6164 KB answer = YES
56 Correct 25 ms 7244 KB answer = YES
57 Correct 24 ms 7032 KB answer = YES
58 Correct 23 ms 6988 KB answer = YES
59 Correct 23 ms 6844 KB answer = YES
60 Correct 26 ms 7224 KB answer = YES
61 Correct 14 ms 6092 KB answer = YES
62 Correct 363 ms 26692 KB answer = NO
63 Correct 406 ms 28200 KB answer = YES
64 Correct 381 ms 28100 KB answer = NO
65 Correct 395 ms 28304 KB answer = YES
66 Correct 8 ms 5404 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB answer = YES
2 Correct 4 ms 4992 KB answer = YES
3 Correct 4 ms 4940 KB answer = YES
4 Correct 4 ms 4940 KB answer = NO
5 Correct 4 ms 5008 KB answer = YES
6 Correct 4 ms 4940 KB answer = YES
7 Correct 5 ms 5000 KB answer = YES
8 Correct 4 ms 4940 KB answer = YES
9 Correct 4 ms 4940 KB answer = NO
10 Correct 4 ms 4940 KB answer = YES
11 Correct 4 ms 4940 KB answer = YES
12 Correct 4 ms 4940 KB answer = NO
13 Correct 4 ms 4940 KB answer = YES
14 Correct 4 ms 4940 KB answer = YES
15 Correct 4 ms 5012 KB answer = YES
16 Correct 4 ms 4940 KB answer = YES
17 Correct 4 ms 4940 KB answer = YES
18 Correct 4 ms 4940 KB answer = YES
19 Correct 4 ms 5012 KB answer = YES
20 Correct 4 ms 4984 KB answer = YES
21 Correct 4 ms 4940 KB answer = YES
22 Correct 4 ms 5008 KB answer = NO
23 Correct 4 ms 5008 KB answer = NO
24 Correct 4 ms 4940 KB answer = YES
25 Correct 4 ms 5012 KB answer = YES
26 Correct 4 ms 4940 KB answer = YES
27 Correct 4 ms 4940 KB answer = YES
28 Correct 4 ms 4940 KB answer = YES
29 Correct 4 ms 4940 KB answer = YES
30 Correct 4 ms 4940 KB answer = NO
31 Correct 4 ms 4940 KB answer = YES
32 Correct 4 ms 4976 KB answer = YES
33 Correct 4 ms 5004 KB answer = YES
34 Correct 4 ms 4940 KB answer = YES
35 Correct 4 ms 4940 KB answer = YES
36 Correct 4 ms 4940 KB answer = YES
37 Correct 4 ms 4940 KB answer = YES
38 Correct 5 ms 4940 KB answer = YES
39 Correct 5 ms 5136 KB answer = YES
40 Correct 6 ms 5196 KB answer = YES
41 Correct 6 ms 5144 KB answer = NO
42 Correct 6 ms 5196 KB answer = YES
43 Correct 6 ms 5196 KB answer = YES
44 Correct 6 ms 5196 KB answer = YES
45 Correct 6 ms 5148 KB answer = YES
46 Correct 5 ms 5068 KB answer = YES
47 Correct 6 ms 5196 KB answer = YES
48 Correct 6 ms 5196 KB answer = YES
49 Correct 26 ms 7240 KB answer = YES
50 Correct 26 ms 7628 KB answer = YES
51 Correct 25 ms 7628 KB answer = YES
52 Correct 20 ms 7100 KB answer = NO
53 Correct 6 ms 5196 KB answer = YES
54 Correct 8 ms 5532 KB answer = YES
55 Correct 14 ms 6164 KB answer = YES
56 Correct 25 ms 7244 KB answer = YES
57 Correct 24 ms 7032 KB answer = YES
58 Correct 23 ms 6988 KB answer = YES
59 Correct 23 ms 6844 KB answer = YES
60 Correct 26 ms 7224 KB answer = YES
61 Correct 14 ms 6092 KB answer = YES
62 Correct 363 ms 26692 KB answer = NO
63 Correct 406 ms 28200 KB answer = YES
64 Correct 381 ms 28100 KB answer = NO
65 Correct 395 ms 28304 KB answer = YES
66 Correct 8 ms 5404 KB answer = YES
67 Correct 216 ms 36140 KB answer = YES
68 Correct 209 ms 35984 KB answer = YES
69 Correct 207 ms 35740 KB answer = YES
70 Correct 349 ms 50624 KB answer = YES
71 Correct 216 ms 35924 KB answer = YES
72 Correct 297 ms 27320 KB answer = YES
73 Correct 298 ms 26724 KB answer = YES
74 Correct 170 ms 23624 KB answer = YES
75 Correct 134 ms 20792 KB answer = NO
76 Correct 30 ms 7628 KB answer = YES
77 Correct 59 ms 10532 KB answer = YES
78 Correct 110 ms 14660 KB answer = YES
79 Correct 248 ms 24000 KB answer = YES
80 Correct 175 ms 24124 KB answer = YES
81 Correct 209 ms 30724 KB answer = NO
82 Correct 280 ms 34932 KB answer = YES
83 Correct 277 ms 35828 KB answer = YES
84 Correct 283 ms 36180 KB answer = YES
85 Correct 215 ms 36156 KB answer = YES
86 Correct 212 ms 35792 KB answer = YES
87 Correct 251 ms 28044 KB answer = NO
88 Correct 341 ms 30144 KB answer = YES
89 Correct 255 ms 25380 KB answer = YES
90 Correct 257 ms 25416 KB answer = YES
91 Correct 253 ms 25412 KB answer = YES
92 Correct 128 ms 15928 KB answer = YES
93 Correct 130 ms 15904 KB answer = YES
94 Correct 222 ms 35468 KB answer = NO
95 Correct 191 ms 25108 KB answer = NO
96 Correct 548 ms 43920 KB answer = YES
97 Correct 156 ms 35512 KB answer = NO