oj.uz

Submission #802785

# Submission time Handle Problem Language Result Execution time Memory
802785 2023-08-02T14:26:40 Z TB_ Graph (BOI20_graph) C++17
100 / 100
 139 ms 27164 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

vvpl adj(100001);
int seen[100001];
vpl res(100001);
vl visited;
int x;

void dfs(int u, int last = -1){
    seen[u] = 1;
    visited.pb(u);
    pl &current = res[u];

    for(auto &[v, w] : adj[u]){
        if(seen[v]){
            if(current.F == res[v].F){ // odd 
                if(x != INF && x != (w-(current.S+res[v].S))/current.F){
                    cout << "NO";
                    exit(0);
                }else x = (w-(current.S+res[v].S))/current.F;
            }else if(current.S + res[v].S != w){
                cout << "NO";
                exit(0);
            }
            continue;
        }
        res[v] = {-current.F, w-current.S};
        dfs(v, u);
    }
}

int main() {
    cout << fixed << setprecision(7);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);

    int n, m, from, to, c;
    cin >> n >> m;
    fo(i, m){
        cin >> from >> to >> c;
        adj[--from].pb({--to, c});
        adj[to].pb({from, c});
    }

    vector<double> ans(n);
    memset(seen, 0, sizeof(seen));
    fo(start, n){
        if(seen[start]) continue;
        visited.clear();
        x = INF;

        res[start] = {1, 0};
        dfs(start);

        if(x != INF){
            for(auto u : visited){
                ans[u] = res[u].F*x*0.5+res[u].S;   
            }
            continue;
        }
        pair<double, double> best = {INF, 0};
        double lo = -1e6;
        double hi = 1e6;
        fo(i, 80){
            double mid1 = lo + (hi-lo) / 3.0;
            double mid2 = hi - (hi-lo) / 3.0;
            double score1 = 0, score2 = 0;
            for(auto u : visited){
                score1 += abs(res[u].F*mid1+res[u].S);
            }
            for(auto u : visited){
                score2 += abs(res[u].F*mid2+res[u].S);
            }
            if(score1<score2) hi = mid2;
            else lo = mid1;
        }
        for(auto u : visited){
            ans[u] = res[u].F*lo+res[u].S;   
        }
    }
    cout << "YES\n";
    fo(i, n) cout << ans[i] << " ";

    return 0;
}

Compilation message

Graph.cpp: In function 'int main()':
Graph.cpp:104:30: warning: variable 'best' set but not used [-Wunused-but-set-variable]
  104 |         pair<double, double> best = {INF, 0};
      |                              ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4564 KB answer = YES
3 Correct 2 ms 4564 KB answer = YES
4 Correct 2 ms 4564 KB answer = NO
5 Correct 2 ms 4564 KB answer = YES
6 Correct 2 ms 4564 KB answer = YES
7 Correct 3 ms 4564 KB answer = YES
8 Correct 3 ms 4564 KB answer = YES
9 Correct 2 ms 4564 KB answer = NO
10 Correct 2 ms 4564 KB answer = YES
11 Correct 2 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 2 ms 4564 KB answer = YES
14 Correct 3 ms 4564 KB answer = YES
15 Correct 2 ms 4564 KB answer = YES
16 Correct 2 ms 4564 KB answer = YES
17 Correct 2 ms 4564 KB answer = YES
18 Correct 3 ms 4564 KB answer = YES
19 Correct 2 ms 4564 KB answer = YES
20 Correct 2 ms 4564 KB answer = YES
21 Correct 2 ms 4564 KB answer = YES
22 Correct 2 ms 4564 KB answer = NO
23 Correct 2 ms 4564 KB answer = NO
24 Correct 2 ms 4564 KB answer = YES
25 Correct 3 ms 4564 KB answer = YES
26 Correct 2 ms 4564 KB answer = YES
27 Correct 2 ms 4564 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 2 ms 4608 KB answer = YES
30 Correct 2 ms 4576 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 2 ms 4564 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 2 ms 4564 KB answer = YES
36 Correct 2 ms 4564 KB answer = YES
37 Correct 2 ms 4564 KB answer = YES
38 Correct 2 ms 4564 KB answer = YES
39 Correct 2 ms 4564 KB answer = YES
40 Correct 3 ms 4692 KB answer = YES
41 Correct 2 ms 4692 KB answer = NO
42 Correct 3 ms 4692 KB answer = YES
43 Correct 3 ms 4692 KB answer = YES
44 Correct 3 ms 4640 KB answer = YES
45 Correct 3 ms 4692 KB answer = YES
46 Correct 3 ms 4644 KB answer = YES
47 Correct 3 ms 4692 KB answer = YES
48 Correct 3 ms 4692 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4564 KB answer = YES
3 Correct 2 ms 4564 KB answer = YES
4 Correct 2 ms 4564 KB answer = NO
5 Correct 2 ms 4564 KB answer = YES
6 Correct 2 ms 4564 KB answer = YES
7 Correct 3 ms 4564 KB answer = YES
8 Correct 3 ms 4564 KB answer = YES
9 Correct 2 ms 4564 KB answer = NO
10 Correct 2 ms 4564 KB answer = YES
11 Correct 2 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 2 ms 4564 KB answer = YES
14 Correct 3 ms 4564 KB answer = YES
15 Correct 2 ms 4564 KB answer = YES
16 Correct 2 ms 4564 KB answer = YES
17 Correct 2 ms 4564 KB answer = YES
18 Correct 3 ms 4564 KB answer = YES
19 Correct 2 ms 4564 KB answer = YES
20 Correct 2 ms 4564 KB answer = YES
21 Correct 2 ms 4564 KB answer = YES
22 Correct 2 ms 4564 KB answer = NO
23 Correct 2 ms 4564 KB answer = NO
24 Correct 2 ms 4564 KB answer = YES
25 Correct 3 ms 4564 KB answer = YES
26 Correct 2 ms 4564 KB answer = YES
27 Correct 2 ms 4564 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 2 ms 4608 KB answer = YES
30 Correct 2 ms 4576 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 2 ms 4564 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 2 ms 4564 KB answer = YES
36 Correct 2 ms 4564 KB answer = YES
37 Correct 2 ms 4564 KB answer = YES
38 Correct 2 ms 4564 KB answer = YES
39 Correct 2 ms 4564 KB answer = YES
40 Correct 3 ms 4692 KB answer = YES
41 Correct 2 ms 4692 KB answer = NO
42 Correct 3 ms 4692 KB answer = YES
43 Correct 3 ms 4692 KB answer = YES
44 Correct 3 ms 4640 KB answer = YES
45 Correct 3 ms 4692 KB answer = YES
46 Correct 3 ms 4644 KB answer = YES
47 Correct 3 ms 4692 KB answer = YES
48 Correct 3 ms 4692 KB answer = YES
49 Correct 10 ms 5612 KB answer = YES
50 Correct 11 ms 5936 KB answer = YES
51 Correct 17 ms 5944 KB answer = YES
52 Correct 5 ms 5332 KB answer = NO
53 Correct 3 ms 4692 KB answer = YES
54 Correct 4 ms 4820 KB answer = YES
55 Correct 6 ms 5076 KB answer = YES
56 Correct 10 ms 5596 KB answer = YES
57 Correct 12 ms 5420 KB answer = YES
58 Correct 11 ms 5416 KB answer = YES
59 Correct 11 ms 5464 KB answer = YES
60 Correct 10 ms 5460 KB answer = YES
61 Correct 8 ms 5032 KB answer = YES
62 Correct 66 ms 16088 KB answer = NO
63 Correct 49 ms 16768 KB answer = YES
64 Correct 45 ms 16736 KB answer = NO
65 Correct 69 ms 16796 KB answer = YES
66 Correct 4 ms 4692 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4564 KB answer = YES
3 Correct 2 ms 4564 KB answer = YES
4 Correct 2 ms 4564 KB answer = NO
5 Correct 2 ms 4564 KB answer = YES
6 Correct 2 ms 4564 KB answer = YES
7 Correct 3 ms 4564 KB answer = YES
8 Correct 3 ms 4564 KB answer = YES
9 Correct 2 ms 4564 KB answer = NO
10 Correct 2 ms 4564 KB answer = YES
11 Correct 2 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 2 ms 4564 KB answer = YES
14 Correct 3 ms 4564 KB answer = YES
15 Correct 2 ms 4564 KB answer = YES
16 Correct 2 ms 4564 KB answer = YES
17 Correct 2 ms 4564 KB answer = YES
18 Correct 3 ms 4564 KB answer = YES
19 Correct 2 ms 4564 KB answer = YES
20 Correct 2 ms 4564 KB answer = YES
21 Correct 2 ms 4564 KB answer = YES
22 Correct 2 ms 4564 KB answer = NO
23 Correct 2 ms 4564 KB answer = NO
24 Correct 2 ms 4564 KB answer = YES
25 Correct 3 ms 4564 KB answer = YES
26 Correct 2 ms 4564 KB answer = YES
27 Correct 2 ms 4564 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 2 ms 4608 KB answer = YES
30 Correct 2 ms 4576 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 2 ms 4564 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 2 ms 4564 KB answer = YES
36 Correct 2 ms 4564 KB answer = YES
37 Correct 2 ms 4564 KB answer = YES
38 Correct 2 ms 4564 KB answer = YES
39 Correct 2 ms 4564 KB answer = YES
40 Correct 3 ms 4692 KB answer = YES
41 Correct 2 ms 4692 KB answer = NO
42 Correct 3 ms 4692 KB answer = YES
43 Correct 3 ms 4692 KB answer = YES
44 Correct 3 ms 4640 KB answer = YES
45 Correct 3 ms 4692 KB answer = YES
46 Correct 3 ms 4644 KB answer = YES
47 Correct 3 ms 4692 KB answer = YES
48 Correct 3 ms 4692 KB answer = YES
49 Correct 10 ms 5612 KB answer = YES
50 Correct 11 ms 5936 KB answer = YES
51 Correct 17 ms 5944 KB answer = YES
52 Correct 5 ms 5332 KB answer = NO
53 Correct 3 ms 4692 KB answer = YES
54 Correct 4 ms 4820 KB answer = YES
55 Correct 6 ms 5076 KB answer = YES
56 Correct 10 ms 5596 KB answer = YES
57 Correct 12 ms 5420 KB answer = YES
58 Correct 11 ms 5416 KB answer = YES
59 Correct 11 ms 5464 KB answer = YES
60 Correct 10 ms 5460 KB answer = YES
61 Correct 8 ms 5032 KB answer = YES
62 Correct 66 ms 16088 KB answer = NO
63 Correct 49 ms 16768 KB answer = YES
64 Correct 45 ms 16736 KB answer = NO
65 Correct 69 ms 16796 KB answer = YES
66 Correct 4 ms 4692 KB answer = YES
67 Correct 91 ms 19660 KB answer = YES
68 Correct 83 ms 19640 KB answer = YES
69 Correct 65 ms 19520 KB answer = YES
70 Correct 99 ms 27164 KB answer = YES
71 Correct 70 ms 19528 KB answer = YES
72 Correct 98 ms 13764 KB answer = YES
73 Correct 86 ms 13756 KB answer = YES
74 Correct 50 ms 13660 KB answer = YES
75 Correct 32 ms 10928 KB answer = NO
76 Correct 18 ms 5844 KB answer = YES
77 Correct 39 ms 6860 KB answer = YES
78 Correct 41 ms 8644 KB answer = YES
79 Correct 107 ms 12404 KB answer = YES
80 Correct 67 ms 13648 KB answer = YES
81 Correct 50 ms 15552 KB answer = NO
82 Correct 79 ms 19188 KB answer = YES
83 Correct 100 ms 20312 KB answer = YES
84 Correct 130 ms 20280 KB answer = YES
85 Correct 104 ms 19736 KB answer = YES
86 Correct 69 ms 19648 KB answer = YES
87 Correct 35 ms 14052 KB answer = NO
88 Correct 92 ms 16100 KB answer = YES
89 Correct 105 ms 12364 KB answer = YES
90 Correct 103 ms 12364 KB answer = YES
91 Correct 71 ms 13004 KB answer = YES
92 Correct 47 ms 9284 KB answer = YES
93 Correct 35 ms 9260 KB answer = YES
94 Correct 64 ms 19136 KB answer = NO
95 Correct 35 ms 11996 KB answer = NO
96 Correct 139 ms 24108 KB answer = YES
97 Correct 39 ms 18604 KB answer = NO