Submission #1208604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208604		agrim_09	Graph (BOI20_graph)	C++20	100 / 100	158 ms	24292 KiB

Graph

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;


// #ifndef ONLINE_JUDGE
// #include "algo/Standard_Stuff/debug.cpp"
// #else
// #define debug(...) 42
// #endif

void judge(){
    srand(time(NULL));
    #ifndef ONLINE_JUDGE
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    #endif
}

// Look for edge cases!!!
signed main(){
    fastio; //judge();
    int n,m; cin >> n >> m;
    vector<vector<pair<int, double>>>adj(n);
    vector<pair<pair<int,int>,int>>edges;
    for(int i = 0,u,v;i<m;i++){
        double w;
        cin >> u >> v >> w; u--; v--;
        if(u>v) swap(u,v);
        edges.pb({{u,v},w});
    }
    int prev_u = -1, prev_v = -1, prev_w = -1;
    sort(all(edges));
    for(auto x : edges){
        int u = x.first.first, v = x.first.second, w = x.second;
        if(u==prev_u and v==prev_v and w!=prev_w){
            cout << "NO"; return 0;
        }
        adj[u].pb({v,w}); adj[v].pb({u,w});
        prev_u = u, prev_v = v, prev_w = w;
    }
    vector<bool>vis(n,false);
    vector<double>ans(n,-1*inf);

    vector<int>b(n,-1*inf); // ax + b
    vector<int>a(n,-1*inf);

    set<int>nodes_in_comp;

    auto dfs = [&](auto &&self, int node)-> double{
        nodes_in_comp.insert(node);
        for(auto [child,w] : adj[node]){
            if(a[child]!=-1*inf){

                if(a[child]+a[node]==0){
                    if(b[child]+b[node]!=w){
                        cout << "NO";
                        exit(0);
                    }
                }
                else{
                    double x = w - b[child] - b[node];
                    double y = a[child] + a[node];
                    return x/y;
                }
                continue;
            }
            a[child] = -1*a[node];
            b[child] = w - b[node];
            double k = self(self,child);
            if(k!=-1*inf){
                return k;
            }
        }
        return -1*inf;
    };

    auto assign = [&](auto&& self, int node)-> bool{
        vis[node] = true;
        for(auto [child,w] : adj[node]){
            if(ans[child]!=-1*inf){
                if(ans[child]+ans[node]!=w){
                    return false;
                }
                continue;
            }
            ans[child] = w - ans[node];
            if(!self(self,child)){
                return false;
            }
        }
        return true;

    };

    for(int i = 0;i<n;i++){
        if(vis[i]){
            continue;
        }
        nodes_in_comp.clear();
        a[i] = 1, b[i] = 0;
        ans[i] = dfs(dfs,i);
        if(ans[i]!=-1*inf){
            if(!assign(assign,i)){
                cout << "NO" << endl; return 0;
            }
            continue;
        }
        vector<double>possible;
        for(auto node : nodes_in_comp){
            double x = -1*b[node], y = a[node];
            possible.pb(x/y);
        }
        sort(all(possible));
        int sz = (int)(possible.size());
        ans[i] = possible[sz/2];
        assign(assign,i);
    }

    cout << "YES" << endl;
    for(auto x : ans) cout << x << ' ';
}

Compilation message (stderr)

Graph.cpp: In function 'void judge()':
Graph.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("1.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Graph.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen("2.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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