제출 #847108

#제출 시각아이디문제언어결과실행 시간메모리
847108Shreyan_PaliwalHarbingers (CEOI09_harbingers)C++17
0 / 100
4 ms3676 KiB
// // #pragma GCC optimize("Ofast") // #include <bits/stdc++.h> // using namespace std; // template<int SZ> struct Tree { // vector<pair<int,int>> adj[SZ]; // void init(int n) { // for (int i = 0; i < n-1; i++) { // int a, b, c; cin >> a >> b >> c; a--, b--; // adj[a].push_back({b,c}); // adj[b].push_back({a,c}); // } // } // }; // #define f first // #define s second // const int maxn = 100005; // int n; // Tree<maxn> tree; // pair<int,int> v[maxn]; // int dist[maxn]; // int ans[maxn]; // struct F { // int a, b; // F() {} // F(int A, int B) : a(A), b(B) { if (b<0) a*=-1, b*=-1; } // bool operator<(F o) const { return a*o.b < b*o.a; } // bool operator<=(F o) const { return a*o.b <= b*o.a; } // }; // struct L { // int m, b; // int operator()(int x) { return m*x + b; } // F operator^(L o) { return F{b-o.b,o.m-m}; } // }; // struct ND { // L v; // ND *l, *r; // ND(int m, int b) { v = L{m, b}; l = r = nullptr; } // ND(ND* _l, ND* _r) { v = L{0, 0}; _l = _r = nullptr; } // }; // struct Node { // L v; // Node *l, *r; // Node(L x) : v(x), l(nullptr), r(nullptr) {} // Node(Node* _l, Node* _r) : l(_l), r(_r) { v = L{0ll, 0ll}; } // }; // template<int SZ> struct PersArray { // Node* roots[SZ]; // int end[SZ]; // Node* build(int l, int r) { // if (l == r) { return new Node(L{0ll, 0ll}); } // int m = (l + r) >> 1; // return new Node(build(l, m), build(m+1, r)); // } // void init() { roots[0] = build(0, n-1); } // Node* UPD(Node* nd, int K, L V, int l, int r) { // if (l == r) { return new Node(V); } // int m = (l + r) >> 1; // if (K <= m) return new Node(UPD(nd->l, K, V, l, m), nd->r); // else return new Node(nd->l, UPD(nd->r, K, V, m+1, r)); // } // L QRY(Node* nd, int K, int l, int r) { // if (l == r) return nd->v; // int m = (l + r) >> 1; // if (K <= m) return QRY(nd->l, K, l, m); // else return QRY(nd->r, K, m+1, r); // return L{0ll, 0ll}; // } // inline L qry(int K, int T) { // return QRY(roots[T], K, 0, n-1); // } // inline void upd(int K, L V, int T, int Tp) { // roots[T] = UPD(roots[Tp], K, V, 0, n-1); // } // }; // struct CHT { // PersArray<maxn> pers; // void add(int nd, int par, L l) { // int sz = pers.end[par]; // while (sz >= 2 && (pers.qry(sz-2,par) ^ l) <= (pers.qry(sz-2,par) ^ pers.qry(sz-1, par))) // sz--; // pers.upd(sz, l, nd, par); // pers.end[nd] = sz + 1; // } // int qry(int nd, int x) { // int lo = 0, hi = pers.end[nd]-1; // while (lo < hi) { // int m = (lo + hi) >> 1; // if (pers.qry(m, nd)(x) > pers.qry(m+1, nd)(x)) // lo = m+1; // else // hi = m; // } // return (pers.qry(lo, nd))(x); // } // }; // CHT cht; // int cnt = 0; // void dfs(int nd, int par, int parst) { // int cur = cnt++; // if (nd != 0) // ans[nd] = v[nd].f + v[nd].s * dist[nd] + cht.qry(parst, v[nd].s); // cht.add(cur, parst, L{-dist[nd], ans[nd]}); // for (auto i : tree.adj[nd]) // if (i.f != par) { // dist[i.f] = dist[nd] + i.s; // dfs(i.f, nd, cur); // } // } // signed main() { // cin.tie(nullptr) -> ios::sync_with_stdio(false); // // freopen("main.in", "r", stdin); // freopen("harbringers.in", "r", stdin); // freopen("harbringers.out", "w", stdout); // cin >> n; // tree.init(n); // for (int i = 1; i < n; i++) cin >> v[i].f >> v[i].s; // cht.pers.init(); // dfs(0, 0, 0); // for (int i = 1; i < n; i++) // cout << ans[i] << ' '; // cout << endl; // return 0; // } // #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; template<typename T> string tostr(const T& value) { ostringstream oss; oss << fixed << setprecision(7); oss << value; return oss.str(); } template<typename... Args> string fstr(const string& format, Args... args) { string result = format; size_t pos = 0; size_t argIndex = 0; auto replaceArg = [&](const auto& arg) { pos = result.find("{}", pos); if (pos != string::npos) { result.replace(pos, 2, tostr(arg)); ++argIndex; } }; (replaceArg(args), ...); return result; } #define int long long const int INF = LLONG_MAX / 2 - INT_MAX; const int INFmem = 0x3f3f3f3f'3f3f3f3f; const int inf = INT_MAX / 2; const int infmem = 0x3f3f3f3f; const int MOD = 1e9 + 7; template<int SZ> struct Tree { vector<pair<int,int>> adj[SZ]; void init(int n) { for (int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; a--, b--; int c; cin >> c; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } } }; const int maxn = 100005; #define f first #define s second int n; Tree<maxn> tree; int ans[maxn]; int dist[maxn]; pair<int,int> v[maxn]; struct F { int a, b; F() {} F(int A, int B) : a(A), b(B) { if (b<0) a*=-1, b*=-1; } bool operator<(F o) const { return a*o.b < b*o.a; } bool operator<=(F o) const { return a*o.b <= b*o.a; } }; struct L { int m, b; int operator()(int x) { return m*x + b; } F operator^(L o) { return F{b-o.b,o.m-m}; } }; L CHT[maxn]; int cht_sz = 0; pair<int,L> removed[maxn]; void add(L l, int nd) { removed[nd] = {0, l}; while (cht_sz >= 2 && (CHT[cht_sz-2]^l) <= (CHT[cht_sz-2]^CHT[cht_sz-1])) { removed[nd].f++; cht_sz--; } swap(removed[nd].s, CHT[cht_sz++]); } int qry(int x) { int lo = 0, hi = cht_sz-1; while (lo < hi) { int m = (lo + hi) >> 1; if (CHT[m](x) > CHT[m+1](x)) lo = m+1; else hi = m; } return CHT[lo](x); } void restore(int nd) { cht_sz--; swap(removed[nd].s, CHT[cht_sz]); cht_sz += removed[nd].f; } void dfs(int nd, int par) { if (nd != 0) ans[nd] = v[nd].f + v[nd].s * dist[nd] + qry(v[nd].s); add(L{-dist[nd], ans[nd]}, par); for (auto i : tree.adj[nd]) if (i.f != par) { dist[i.f] = dist[nd] + i.s; dfs(i.f, nd); restore(nd); } } void solve() { cin >> n; tree.init(n); for (int i = 1; i < n; i++) cin >> v[i].f >> v[i].s; dfs(0, 0); for (int i = 1; i < n; i++) cout << ans[i] << ' '; cout << endl; } // #define LOCAL // #define CODEFORCES signed main() { #ifndef LOCAL cin.tie(nullptr) -> ios::sync_with_stdio(false); freopen("harbringers.in", "r", stdin); freopen("harbringers.out", "w", stdout); #endif #ifdef LOCAL freopen("main.in", "r", stdin); #endif int t; #ifdef CODEFORCES cin >> t; #endif #ifndef CODEFORCES t=1; #endif for (int i = 1; i <= t; i++) { #ifdef LOCAL cout << fstr("----- Case {} -----", i) << endl; auto startTime = clock(); #endif solve(); #ifdef LOCAL cout << fstr("RUNTIME: {}", (double)(clock() - startTime)/CLOCKS_PER_SEC) << endl; cout << fstr("----- END CASE {} -----", i) << endl; #endif #ifdef LOCAL #endif } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp: In function 'void solve()':
harbingers.cpp:265:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  265 |     for (int i = 1; i < n; i++) cout << ans[i] << ' '; cout << endl;
      |     ^~~
harbingers.cpp:265:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  265 |     for (int i = 1; i < n; i++) cout << ans[i] << ' '; cout << endl;
      |                                                        ^~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:273:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |     freopen("harbringers.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:274:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |     freopen("harbringers.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...