Submission #1178476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178476		InvMOD	Graph (BOI20_graph)	C++20	100 / 100	85 ms	19136 KiB

Graph

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()

const int N = 1e5 + 1;

int n, m, a[N], b[N];

bool vis[N], found; double val, ans[N];

vector<pair<int,int>> adj[N]; vector<int> comp;

void dfs(int x){
    vis[x] = true, comp.push_back(x);

    for(pair<int,int> e : adj[x]){
        int v = e.first, w = e.second;
        if(!vis[v]){
            a[v] = -a[x];
            b[v] = w - b[x];
            dfs(v);
        }
        else{
            if(a[v] == -a[x]){
                if(b[x] + b[v] != w){
                    cout << "NO\n"; exit(0);
                }
            }
            else{
                if(!found){
                    // find x that make current v and ideal v be the same
                    val = (1.0l * b[v] - (w - b[x])) / (1.0l * (-a[x]) - a[v]);
                    found = true;
                }
                else{
                    double cur_val = (1.0l * b[v] - (w - b[x])) / (1.0l * (-a[x]) - a[v]);
                    if(cur_val != val){
                        cout << "NO\n"; exit(0);
                    }
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("InvMOD.INP", "r", stdin);
    //freopen("InvMOD.OUT", "w", stdout);

    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        int u,v,c; cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }

    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            found = false, comp.clear();

            a[i] = 1, b[i] = 0;
            dfs(i);

            if(found){
                for(const int &x : comp){
                    ans[x] = (1.0l * a[x]) * val + (1.0l * b[x]);
                }
            }
            else{
                sort(all(comp), [&](int x, int y){
                    return (-a[x] * b[x]) < (-a[y] * b[y]);
                });

                val = -a[comp[sz(comp) / 2]] * b[comp[sz(comp) / 2]];
                for(const int& x : comp){
                    ans[x] = (1.0l * a[x]) * val + (1.0l * b[x]);
                }
            }
        }
    }

    cout << "YES\n";
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    } cout << "\n";

    //cerr << (double) clock() / CLOCKS_PER_SEC * 1000 << " ms\n";
}

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