oj.uz

답안 #802781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
802781 2023-08-02T14:24:12 Z TB_ Graph (BOI20_graph) C++17
17 / 100
 4 ms 4692 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(20);
    // 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4636 KB answer = YES
3 Correct 3 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 2 ms 4564 KB answer = YES
8 Correct 3 ms 4588 KB answer = YES
9 Correct 2 ms 4644 KB answer = NO
10 Correct 2 ms 4644 KB answer = YES
11 Correct 3 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 4 ms 4564 KB answer = YES
14 Correct 2 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 2 ms 4564 KB answer = YES
19 Correct 3 ms 4692 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4636 KB answer = YES
3 Correct 3 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 2 ms 4564 KB answer = YES
8 Correct 3 ms 4588 KB answer = YES
9 Correct 2 ms 4644 KB answer = NO
10 Correct 2 ms 4644 KB answer = YES
11 Correct 3 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 4 ms 4564 KB answer = YES
14 Correct 2 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 2 ms 4564 KB answer = YES
19 Correct 3 ms 4692 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 4 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 4636 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 3 ms 4564 KB answer = YES
30 Correct 3 ms 4564 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 3 ms 4636 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 3 ms 4564 KB answer = YES
36 Correct 2 ms 4564 KB answer = YES

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4636 KB answer = YES
3 Correct 3 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 2 ms 4564 KB answer = YES
8 Correct 3 ms 4588 KB answer = YES
9 Correct 2 ms 4644 KB answer = NO
10 Correct 2 ms 4644 KB answer = YES
11 Correct 3 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 4 ms 4564 KB answer = YES
14 Correct 2 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 2 ms 4564 KB answer = YES
19 Correct 3 ms 4692 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 4 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 4636 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 3 ms 4564 KB answer = YES
30 Correct 3 ms 4564 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 3 ms 4636 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 3 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 4640 KB answer = YES
39 Correct 4 ms 4644 KB answer = YES
40 Correct 3 ms 4692 KB answer = YES
41 Correct 2 ms 4692 KB answer = NO
42 Correct 4 ms 4692 KB answer = YES
43 Incorrect 3 ms 4648 KB participant answer is larger than the answer of jury
44 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4636 KB answer = YES
3 Correct 3 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 2 ms 4564 KB answer = YES
8 Correct 3 ms 4588 KB answer = YES
9 Correct 2 ms 4644 KB answer = NO
10 Correct 2 ms 4644 KB answer = YES
11 Correct 3 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 4 ms 4564 KB answer = YES
14 Correct 2 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 2 ms 4564 KB answer = YES
19 Correct 3 ms 4692 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 4 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 4636 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 3 ms 4564 KB answer = YES
30 Correct 3 ms 4564 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 3 ms 4636 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 3 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 4640 KB answer = YES
39 Correct 4 ms 4644 KB answer = YES
40 Correct 3 ms 4692 KB answer = YES
41 Correct 2 ms 4692 KB answer = NO
42 Correct 4 ms 4692 KB answer = YES
43 Incorrect 3 ms 4648 KB participant answer is larger than the answer of jury
44 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB answer = YES
2 Correct 2 ms 4636 KB answer = YES
3 Correct 3 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 2 ms 4564 KB answer = YES
8 Correct 3 ms 4588 KB answer = YES
9 Correct 2 ms 4644 KB answer = NO
10 Correct 2 ms 4644 KB answer = YES
11 Correct 3 ms 4564 KB answer = YES
12 Correct 2 ms 4564 KB answer = NO
13 Correct 4 ms 4564 KB answer = YES
14 Correct 2 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 2 ms 4564 KB answer = YES
19 Correct 3 ms 4692 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 4 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 4636 KB answer = YES
28 Correct 2 ms 4564 KB answer = YES
29 Correct 3 ms 4564 KB answer = YES
30 Correct 3 ms 4564 KB answer = NO
31 Correct 2 ms 4564 KB answer = YES
32 Correct 2 ms 4564 KB answer = YES
33 Correct 3 ms 4636 KB answer = YES
34 Correct 3 ms 4564 KB answer = YES
35 Correct 3 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 4640 KB answer = YES
39 Correct 4 ms 4644 KB answer = YES
40 Correct 3 ms 4692 KB answer = YES
41 Correct 2 ms 4692 KB answer = NO
42 Correct 4 ms 4692 KB answer = YES
43 Incorrect 3 ms 4648 KB participant answer is larger than the answer of jury
44 Halted 0 ms 0 KB -