Submission #400033

#	Time	Username	Problem	Language	Result	Execution time	Memory
400033		hltk	Harbingers (CEOI09_harbingers)	C++17	Compilation error	0 ms	0 KiB

harbingers

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("arch=skylake")
#include <bits/stdc++.h>
using namespace std;
const long INF = 1e18;
int n, s[100100], t[100100];
vector<pair<int, int>> g[100100];
int sz[100100];
void dfs_sz(int u) {
	sz[u] = 1;
	for (auto &p : g[u]) {
		int v = p.first;
		g[v].erase(find_if(g[v].begin(), g[v].end(), [&](auto a) {
			return a.first == u;
		}));
		dfs_sz(v);
		if (sz[v] > sz[g[u][0].first]) swap(p, g[u][0]);
		sz[u] += sz[v];
	}
}
long dp[100100];
struct Line {
	long m, c;
	long operator()(long x) { return m * x + c; }
};
long intersect(Line a, Line b) {
	long num = b.c - a.c, dem = a.m - b.m;
	return num / dem - ((num ^ dem) < 0 && num % dem);
}
vector<pair<long, Line>> cht{{-INF, {0, 0}}};
vector<Line> st;
long query(long x) {
	long ret = prev(lower_bound(cht.begin(), cht.end(), pair{x, Line{}}, [&](auto a, auto b) {
		return a.first < b.first;
	}))->second(x);
	for (auto u : st) ret = max(ret, u(x));
	return ret;
}
void dfs(int u, long cd, bool heavy) {
	vector<Line> popped;
	if (u != 1) {
		dp[u] = -query(t[u]) + cd * t[u] + s[u];
		auto l = Line{cd, -dp[u]};
		if (heavy) {
			while ((int) cht.size() >= 2) {
				auto a = cht[cht.size() - 2].second;
				auto b = cht[cht.size() - 1].second;
				if (intersect(a, b) >= intersect(b, l)) {
					popped.push_back(cht.back().second);
					cht.pop_back();
				} else break;
			}
			cht.emplace_back(intersect(cht.back().second, l), l);
		} else {
			st.push_back(l);
		}
	}
	for (auto [v, d] : g[u]) {
		dfs(v, cd + d, v == g[u][0].first);
	}
	if (u != 1) {
		if (heavy) {
			cht.pop_back();
			while (!popped.empty()) {
				cht.emplace_back(intersect(cht.back().second, popped.back()), popped.back());
				popped.pop_back();
			}
		} else {
			st.pop_back();
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1, u, v, d; i <= n - 1; ++i) {
		scanf("%d %d %d", &u, &v, &d);
		g[u].emplace_back(v, d);
		g[v].emplace_back(u, d);
	}
	for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
	dfs_sz(1);
	dfs(1, 0, 1);
	for (int i = 2; i <= n; ++i) printf("%ld%c", dp[i], i == n ? '\n' : ' ');
}
// f_j(x) := -dp[j] + dep[j] * x
//   dp[j] + (d - x) t_i + s_i
// = dp[j] - x * t_i + d * t_i + s_i
// = -f_j(t_i) + d * t_i + s_i

Compilation message (stderr)

In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr.h:148,
                 from /usr/include/c++/9/ext/atomicity.h:35,
                 from /usr/include/c++/9/bits/ios_base.h:39,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from harbingers.cpp:3:
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("arch=") was already specified
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("arch=") was already specified
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("arch=") was already specified
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("arch=") was already specified
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("arch=") was already specified
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("arch=") was already specified
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("arch=") was already specified
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("arch=") was already specified
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("arch=") was already specified
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("arch=") was already specified
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("arch=") was already specified
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("arch=") was already specified
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("arch=") was already specified
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("arch=") was already specified
  121 | __gthrw(pthread_mutex_unlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("arch=") was already specified
  122 | __gthrw(pthread_mutex_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("arch=") was already specified
  123 | __gthrw(pthread_mutex_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("arch=") was already specified
  125 | __gthrw(pthread_cond_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("arch=") was already specified
  126 | __gthrw(pthread_cond_broadcast)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("arch=") was already specified
  127 | __gthrw(pthread_cond_signal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("arch=") was already specified
  128 | __gthrw(pthread_cond_wait)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("arch=") was already specified
  129 | __gthrw(pthread_cond_timedwait)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("arch=") was already specified
  130 | __gthrw(pthread_cond_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("arch=") was already specified
  132 | __gthrw(pthread_key_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("arch=") was already specified
  133 | __gthrw(pthread_key_delete)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("arch=") was already specified
  134 | __gthrw(pthread_mutexattr_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("arch=") was already specified
  135 | __gthrw(pthread_mutexattr_settype)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("arch=") was already specified
  136 | __gthrw(pthread_mutexattr_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("arch=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("arch=") was already specified
  237 | __gthrw2(__gthrw_(__pthread_key_create),
      | ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:71:3: error: option("arch=") was already specified
   71 |   _GLIBCXX_GTHRW(rwlock_rdlock)
      |   ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:71:3: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:72:3: error: option("arch=") was already specified
   72 |   _GLIBCXX_GTHRW(rwlock_tryrdlock)
      |   ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:72:3: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:73:3: error: option("arch=") was already specified
   73 |   _GLIBCXX_GTHRW(rwlock_wrlock)
      |   ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:73:3: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:74:3: error: option("arch=") was already specified
   74 |   _GLIBCXX_GTHRW(rwlock_trywrlock)
      |   ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:74:3: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:75:3: error: option("arch=") was already specified
   75 |   _GLIBCXX_GTHRW(rwlock_unlock)
      |   ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:75:3: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:89:4: error: option("arch=") was already specified
   89 |    __gthrw(pthread_rwlock_timedrdlock);
      |    ^~~~~~~
/usr/include/c++/9/shared_mutex:89:4: error: option("arch=") was already specified
/usr/include/c++/9/shared_mutex:99:4: error: option("arch=") was already specified
   99 |    __gthrw(pthread_rwlock_timedwrlock);
      |    ^~~~~~~
/usr/include/c++/9/shared_mutex:99:4: error: option("arch=") was already specified
harbingers.cpp: In function 'int main()':
harbingers.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  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:36: 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, t + i);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~