Submission #732203

#	Time	Username	Problem	Language	Result	Execution time	Memory
732203		dxz05	Graph (BOI20_graph)	C++17	0 / 100	33 ms	47316 KiB

Graph

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e6 + 3e2;

vector<pair<int, int>> g[N];
pair<int, int> dp[N];
vector<pair<int, int>> equations[N];

pair<int, int> f(int t, pair<int, int> a){
    return make_pair(-a.first, t - a.second);
}

bool used[N];
vector<int> comp;
void dfs(int v){
    used[v] = true;
    comp.push_back(v);

    equations[v].push_back(dp[v]);

    for (auto [u, x] : g[v]){
        if (!used[u]) {
            dp[u] = f(x, dp[v]);
            dfs(u);
        }

        equations[v].push_back(f(x, dp[u]));
    }
}

bool check(pair<int, int> sol){
    for (int v : comp){
        for (auto [u, x] : g[v]){
            if ((dp[v].first + dp[u].first) * sol.first != (x - dp[v].second - dp[u].second) * sol.second){
                return false;
            }
        }
    }
    return true;
}

long double val[N];

void solve(){
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        int u, v, x;
        cin >> u >> v >> x;
        g[u].emplace_back(v, x);
        g[v].emplace_back(u, x);
    }

    for (int t = 1; t <= n; t++){
        if (used[t]) continue;
        comp.clear();
        dp[t] = make_pair(1, 0);
        dfs(t);

        pair<int, int> sol(0, 1);
        bool found = false;

        for (int v : comp){
            for (int i = 0; i + 1 < equations[v].size(); i++){
                auto p = equations[v][i];
                auto q = equations[v][i + 1];
                if (p == q) continue;

                int a = q.second - p.second;
                int b = p.first - q.first;

                if (b == 0){
                    cout << "NO" << endl;
                    return;
                }

                if (a < 0) a *= -1, b *= -1;
                if (a == 0) b = 1;

                int gg = __gcd(a, b);
                a /= gg, b /= gg;

                if (!found){
                    found = true;
                    sol = MP(a, b);
                } else if (sol != MP(a, b)){
                    cout << "NO" << endl;
                    return;
                }

            }
        }

        if (!found){
            long double mn = 1e9;

            vector<pair<int, int>> values{
                {0, 1}, {1, 2}, {1, 1}, {2, 1}, {3, 2},
                {-1, 2}, {-1, 1}, {-2, 1}, {-3, 2}
            };

            for (auto p : values){
                if (!check(p)) continue;

                long double cur = 0;
                for (int v : comp){
                    long double _val = (long double) dp[v].first * p.first / p.second + dp[v].second;
                    cur += fabsl(_val);
                }

                if (cur < mn){
                    mn = cur;
                    sol = p;
                    found = true;
                }
            }
        }

        if (!found || !check(sol)){
            cout << "NO" << endl;
            return;
        }

        for (int v : comp){
            val[v] = (long double) dp[v].first * sol.first / sol.second + dp[v].second;
        }

    }

    cout << setprecision(7);

    cout << "YES" << endl;
    for (int i = 1; i <= n; i++){
        cout << val[i] << ' ';
    }
    cout << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
    // cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;

    return 0;
}

Compilation message (stderr)

Graph.cpp: In function 'void solve()':
Graph.cpp:81:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for (int i = 0; i + 1 < equations[v].size(); i++){
      |                             ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42