제출 #848637

#제출 시각아이디문제언어결과실행 시간메모리
848637lovrotHarbingers (CEOI09_harbingers)C++17
90 / 100
88 ms22768 KiB
#include <cstdio> #include <algorithm> #include <vector> #include <cassert> #define MP make_pair #define X first #define Y second #define EB emplace_back using namespace std; typedef long long ll; struct dot { ll x, y; dot() {} dot(ll x, ll y) : x(x), y(y) {} ll operator* (const dot d) const { return x * d.x + y * d.y; } }; ll ccw(const dot &a, const dot &b, const dot &c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } const int N = 1e5 + 10; ll SIZ[N], DP[N]; ll S[N], V[N]; dot HL[N]; ll query(int u) { dot d = dot(V[u], 1); int lo = 0, hi = SIZ[u]; while(hi - lo > 1) { int mi = (lo + hi) / 2; if(HL[mi] * d < HL[mi + 1] * d) hi = mi; else lo = mi; } return min(HL[lo] * d, HL[hi] * d); } bool BIO[N]; dot DWN[N]; vector<pair<int, ll>> G[N]; void dp(int u, ll d) { if(u != 1) DP[u] = S[u] + V[u] * d + query(u); BIO[u] = 1; dot q = dot(-d, DP[u]); int lo = -1, hi = SIZ[u]; while(hi - lo > 1) { int mi = (lo + hi) / 2; if(ccw(HL[mi], HL[mi + 1], q) > 0) hi = mi; else lo = mi; } DWN[u] = HL[hi + 1]; HL[hi + 1] = q; for(pair<int, ll> e : G[u]) { int v = e.X; if(!BIO[v]) { SIZ[v] = hi + 1; dp(v, d + e.Y); } } HL[hi + 1] = DWN[u]; } int n; int main() { scanf("%d", &n); for(int i = 0; i < n - 1; ++i) { int u, v, d; scanf("%d%d%d", &u, &v, &d); G[u].EB(MP(v, d)); G[v].EB(MP(u, d)); } for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i); SIZ[1] = -1; dp(1, 0); for(int i = 2; i <= n; ++i) printf("%lld%c", DP[i], " \n"[i == n]); return 0; }

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

harbingers.cpp: In function 'int main()':
harbingers.cpp:80:38: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   80 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                                     ~^     ~~~~~
      |                                      |       |
      |                                      int*    ll* {aka long long int*}
      |                                     %lld
harbingers.cpp:80:40: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   80 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                                       ~^          ~~~~~
      |                                        |            |
      |                                        int*         ll* {aka long long int*}
      |                                       %lld
harbingers.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d%d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:80:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for(int i = 2; i <= n; ++i) scanf("%d%d", S + i, V + i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...