Submission #1277542

#TimeUsernameProblemLanguageResultExecution timeMemory
1277542faricaGraph (BOI20_graph)C++20
100 / 100
81 ms21380 KiB
#include<bits/stdc++.h> using namespace std; using vi = vector<int>; using pi = pair<int,int>; typedef long long ll; #define debug(x) cout << #x << " = " << x << "\n"; #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; const int MOD = 1e9; /* template<ll mod> struct modnum { static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); using S = conditional_t<is_big_mod, ll, int>; using L = conditional_t<is_big_mod, __int128, ll>; S x; modnum() : x(0) {} modnum(ll _x) { _x %= static_cast<ll>(mod); if (_x < 0) { _x += mod; } x = _x; } modnum pow(ll n) const { modnum res = 1; modnum cur = *this; while (n > 0) { if (n & 1) res *= cur; cur *= cur; n /= 2; } return res; } modnum inv() const { return (*this).pow(mod-2); } modnum& operator+=(const modnum& a){ x += a.x; if (x >= mod) x -= mod; return *this; } modnum& operator-=(const modnum& a){ if (x < a.x) x += mod; x -= a.x; return *this; } modnum& operator*=(const modnum& a){ x = static_cast<L>(x) * a.x % mod; return *this; } modnum& operator/=(const modnum& a){ return *this *= a.inv(); } friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } }; using mint = modnum<MOD>; template <class T> class SumSegmentTree { private: const T DEFAULT = 0; vector<T> segtree; int len; public: SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {} void set(int ind, T val) { ind += len; segtree[ind] = val; for (; ind > 1; ind /= 2) { segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1]; } } T range_sum(int start, int end) { T sum = DEFAULT; for (start += len, end += len; start < end; start /= 2, end /= 2) { if (start % 2 == 1) { sum += segtree[start++]; } if (end % 2 == 1) { sum += segtree[--end]; } } return sum; } }; struct DSU{ vector<int> p, sz, used, mn, mx; DSU(int n){ p.assign(n, 0); sz.assign(n, 1); used.assign(n, 0); mx.assign(n, 0); mn.assign(n, 0); for (int i = 0; i < n; i++) p[i] = i; } int find(int u){ if (p[u] == u) return u; p[u] = find(p[u]); return p[u]; } void unite(int u, int v){ u = find(u); v = find(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); p[v] = u; sz[u] += sz[v]; used[u] += used[v]; mn[u] = min(mn[u], mn[v]); mx[u] = max(mx[u], mx[v]); } bool same(int u, int v){ return find(u) == find(v); } int size(int u){ u = find(u); return sz[u]; } }; const int N = 250005; struct BIT { ll b[N], n; void init(int _n) { n = _n ; for(int i = 0 ; i <= n ; ++i) b[i] = 0; } inline int lowbit(int x) { return x & (-x); } void update(int x, ll v) { for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v; } ll query(int x) { ll ans = 0; for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i]; return ans; } } bit[2]; */ const float INF = 1e9; int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1 x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1; } int inv_ecd(int a, int m) { int x, y; int g = gcd(a, m, x, y); if(g != 1) return -1; x = (x + m) % m; return x; } vector<vector<pi>>adjL; map<int,int>ma; vector<bool>vis; vector<pi>val; vector<float> ans; bool FND; float FND_X; void set_ans(int pos) { vis[pos] = 1; for(pi adj: adjL[pos]) { if(ans[adj.first] != INF) continue; ans[adj.first] = adj.second - ans[pos]; set_ans(adj.first); } } void dfs(int pos, int add, int sign, int prev) { val[pos] = {add,sign}; vis[pos] = 1; bool tmp1 = (add >= 0), tmp2 = (sign >= 0); if(tmp1 == tmp2) ++ma[abs(add)]; else ++ma[-abs(add)]; for(pi adj: adjL[pos]) { if(vis[adj.first]) { if(adj.first == prev) continue; if(val[adj.first].second == sign) { FND = 1; FND_X = (float)(adj.second - add - val[adj.first].first) / 2; FND_X *= sign; } continue; } dfs(adj.first, adj.second - add, (sign == 1 ? -1 : 1), pos); } } void solve() { int n, m; cin >> n >> m; adjL.resize(n, vector<pi>()); vis.assign(n, 0); val.resize(n); ans.assign(n, INF); vi V; for(int i=0; i<m; ++i) { int a, b, c; cin >> a >> b >> c; --a, --b; if(a == b) { ans[a] = (float)c/2; V.push_back(a); continue; } adjL[a].push_back({b,c}); adjL[b].push_back({a,c}); } for(int x: V) { set_ans(x); } for(int i=0; i<n; ++i) { if(vis[i]) continue; ma.clear(); FND = 0; dfs(i, 0, 1, i); if(FND) { ans[i] = FND_X; set_ans(i); continue; } ll L = 0, R = 0, mi, x, R2 = 0, L2 = 0; int pos, prev; for(auto it = ma.begin(); it != ma.end(); ++it) { //cout << it->first << " - " << it->second << endl; if(it == ma.begin()) pos = it->first, prev = it->second; else { R += it->second * (it->first - pos); R2 += it->second; } } mi = R; x = (ma.begin())->first; auto it = ma.begin(); ++it; for(; it != ma.end(); ++it) { R -= (it->first - pos) * R2; R2 -= it->second; L2 += prev; L += (it->first - pos) * L2; prev = it->second; pos = it->first; if((L+R) < mi) { mi = L+R; x = it->first; } } ans[i] = -x; set_ans(i); } for(int i=0; i<n; ++i) { for(pi adj: adjL[i]) { if((ans[i] + ans[adj.first]) != adj.second) { cout << "NO" << endl; return; } } } cout << "YES" << endl; for(float x: ans) cout << x << " "; cout << endl; } int main(){ //freopen("xortransform.in", "r", stdin); //freopen("xortransform.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...