QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#532756#6660. 택시 여행orz_z0 253ms51276kbC++146.0kb2024-08-25 11:17:582024-08-25 11:17:59

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 11:17:59]
  • 评测
  • 测评结果:0
  • 用时:253ms
  • 内存:51276kb
  • [2024-08-25 11:17:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
template<typename T> void debug(string s, T x) {cerr << "[" << s << "] = [" << x << "]\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i = 0, b = 0; i < (int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++;else if (s[i] == ')' || s[i] == '}') b--;else if (s[i] == ',' && b == 0) {cerr << "[" << s.substr(0, i) << "] = [" << x << "] | ";debug(s.substr(s.find_first_not_of(' ', i + 1)), args...);break;}}
#ifdef ONLINE_JUDGE
#define Debug(...)
#else
#define Debug(...) debug(#__VA_ARGS__, __VA_ARGS__)
#endif
#define pb push_back
#define fi first
#define se second
#define Mry fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
	int x = 0;
	bool t = 0;
	char c = getchar();
	while (c < '0' || c > '9') t |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return t ? -x : x;
}
inline void wi(int x) {
	if (x < 0) {
		putchar('-'), x = -x;
	}
	if (x > 9) wi(x / 10);
	putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
	wi(x), putchar(s);
}
bool Mbe;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;


bool Med;

int n, tot, head[_], to[_ << 1], nxt[_ << 1], w[_ << 1];

void add(int u, int v, int c) {
	to[++tot] = v, nxt[tot] = head[u], head[u] = tot, w[tot] = c;
}

namespace Dis {
	int dfn[_], cnt, Fa[_], st[_][20];
	ll dep[_];
	void dfs(int u, int fa) {
		dfn[u] = ++cnt;
		Fa[u] = fa;
		st[dfn[u]][0] = u;
		for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i]) if(v != fa) {
			dep[v] = dep[u] + w[i];
			dfs(v, u);
		}
	}
	int get(int x, int y) {
		return dfn[Fa[x]] < dfn[Fa[y]] ? x : y;
	}
	int lg[_];
	int LCA(int u, int v) {
		if(u == v) return u;
		u = dfn[u], v = dfn[v];
		if(u > v) swap(u, v);
		u++;
		int t = lg[v - u + 1];
		return Fa[get(st[u][t], st[v - (1 << t) + 1][t])];
	}
	ll Dis(int u, int v) {
//		Debug(u, v, LCA(u, v));
		return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);
	}
	void init() {
		F(i, 2, n) lg[i] = lg[i >> 1] + 1;
		dfs(1, 0);
		F(j, 1, lg[n]) {
			F(i, 1, n - (1 << j) + 1) st[i][j] = get(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
}

ll f[_];

int Sum, rt, sz[_]; bool vis[_];
void get_rt(int u, int fa) {
	int mx = 0;
	for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i]) if(v != fa &&!vis[v]) {
		get_rt(v, u);
		mx = max(mx, sz[v]);
	}
	mx = max(mx, Sum - sz[u]);
	if(mx <= Sum / 2) {
		rt = u;
	}
}
void get_sz(int u, int fa) {
	sz[u] = 1;
	for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i]) if(v != fa && !vis[v]) {
		get_sz(v, u);
		sz[u] += sz[v];
	}
}
int Fa[_];
void work(int u) {
//	Debug(u);
	vis[u] = 1;
	for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i]) if(!vis[v]) {
		get_sz(v, u);
		Sum = sz[v];
		get_rt(v, u);
		Fa[rt] = u;
		work(rt);
	}
}
pair<ll, ll> operator - (pair<ll, ll> a, pair<ll, ll> b) {
	return make_pair(a.fi - b.fi, a.se - b.se);
}
struct Tubao {
	vector<pair<ll, ll>> a;
	void ins(ll x, ll y) {
		if(a.empty()) {
			a.pb({x, y});
			return;
		}
		while(a.size() > 1 && 1ll * (a.back().se - a[(int)a.size() - 2].se) * (x - a.back().fi) < 1ll * (a.back().fi - a[(int)a.size() - 2].fi) * (y - a.back().se)) a.pop_back();
		a.pb({x, y});
	}
	ll qry(ll x) {
		if(a.empty()) {
			return inf;
		}
//		ll res = inf;
//		for(pii v : a) res = min(res, v.fi * x + v.se);
//		return res;
		if((int)a.size() == 1) {
			return a.front().fi * x + a.front().se;
		}
		int l = 1, r = (int)a.size() - 1, mid, res = 0;
		while(l <= r) {
			mid = (l + r) >> 1;
			if((a[mid].se - a[mid - 1].se) <= (a[mid].fi - a[mid - 1].fi) * (-x)) {
				l = mid + 1;
				res = mid;
			} else {
				r = mid - 1;
			}
		}
		return a[res].fi * x + a[res].se;
	}
} d[_];
ll a[_], b[_];
void ins(int u) {
	for(int nw = u; nw; nw = Fa[nw]) {
		d[nw].ins(a[u], f[u] + a[u] * Dis::Dis(u, nw) + b[u]);
	}
}
ll qry(int u) {
	ll res = inf;
	for(int nw = u; nw; nw = Fa[nw]) {
		res = min(res, d[nw].qry(Dis::Dis(u, nw)));
	}
	return res;
}

int p[_];

vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W) {
	n = A.size();
	F(i, 1, n) a[i] = B[i - 1], b[i] = A[i - 1];
	F(i, 0, n - 2) {
		U[i]++, V[i]++;
		add(U[i], V[i], W[i]);
		add(V[i], U[i], W[i]);
	}
	Dis::init();
//	Debug("Yes");
	f[1] = 0;
	F(i, 2, n) f[i] = a[1] * Dis::Dis(1, i) + b[1];
//	Debug("2");
	Sum = n;
	get_sz(1, 0);
	get_rt(1, 0);
	work(rt);
//	Debug("done");
	F(i, 1, n) p[i] = i;
	sort(p + 1, p + n + 1, [&](int a1, int b1) { return a[a1] > a[b1]; });
	ins(1);
//	F(i, 2, n) Debug(i, f[i], Dis::Dis(1, i));
	F(i, 1, n) {
		if(p[i] == 1) continue;
//		Debug(p[i], f[p[i]], qry(p[i]));
		f[p[i]] = qry(p[i]);
		ins(p[i]);
//		Debug(qry(p[i]));
	}
//	F(i, 1, n) {
//		Debug(i, qry(i));
//	}
	vector<ll> f2;
	F(i, 2, n) f2.pb(qry(i));
	return f2;
}

//signed main() {
//	// Mry;
//	travel({10, 5, 13, 4, 3}, {10, 7, 5, 9, 1}, {1, 0, 3, 2}, {0, 2, 2, 4}, {1, 5, 10, 3});
//	// Try;
//	return 0;
//}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 0ms
memory: 20232kb

input:

2
684124582850 713748627948
74361 256955
0 1 661088

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
733283747618
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 3 lines

Test #2:

score: 7
Accepted
time: 0ms
memory: 22376kb

input:

3
251115773325 363097865287 358609487841
826785 213106 914768
0 1 851938
2 0 231697

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
955485332655
442679377470
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 4 lines

Test #3:

score: 7
Accepted
time: 3ms
memory: 22556kb

input:

3
489998888627 318672977903 70353752652
258347 458793 258657
2 1 156120
0 2 524840

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
665922861747
625589728107
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 4 lines

Test #4:

score: 7
Accepted
time: 4ms
memory: 24344kb

input:

3
737471938521 315388610250 818943569900
726908 666797 564862
0 1 460302
0 2 785280

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
1072069144737
1308298252761
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 4 lines

Test #5:

score: 7
Accepted
time: 0ms
memory: 22276kb

input:

4
201836820267 208957719162 992553400562 566050337171
243994 65303 590123 936951
1 0 259719
0 3 860376
3 2 513584

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
265206697953
537074816507
411763402011
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 5 lines

Test #6:

score: 7
Accepted
time: 0ms
memory: 20288kb

input:

4
440719935569 160237864481 704297665373 767778991240
451998 371509 46564 828427
1 0 861960
1 3 830699
2 3 185693

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
830324131649
1289731282865
1205798418251
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 5 lines

Test #7:

score: 7
Accepted
time: 0ms
memory: 24368kb

input:

5
148262899914 9382086008 622202345986 443806901161 213829280326
178155 503016 333953 572340 461148
0 3 453941
3 2 84057
4 0 171136
3 1 598794

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
335812903839
244109933604
229134758769
178751633994
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 6 lines

Test #8:

score: 7
Accepted
time: 0ms
memory: 20288kb

input:

5
391440982512 969252165920 333946610796 649830522527 902812044171
522045 996458 225429 545971 667483
0 1 701500
0 4 514779
2 1 435377
3 0 919439

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
757655550012
984941935977
871429515267
660178785567
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 6 lines

Test #9:

score: 7
Accepted
time: 4ms
memory: 24456kb

input:

17
315015458526 65513576283 829720084774 654640079244 561177336848 463903843105 496216524512 837433489064 92734412345 807145138979 250511786518 915329126804 373916658654 78276842047 121976569238 432447179015 519384539551
696133 642473 231377 987220 589587 337763 790202 785083 249580 108311 73808 892...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
430639669161
417840567823
403532946274
499079112962
498466070651
495984520010
499402357184
501387707132
498265325456
501233852966
474661031682
494612046266
411867746683
497598865088
499819422548
496976423075
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

ok 18 lines

Test #10:

score: 0
Wrong Answer
time: 3ms
memory: 20364kb

input:

20
764145449871 794297102632 450082553736 427358261877 587251097098 98567356955 15910789509 321286084089 25839798358 969219436118 975479420690 937908953492 410498404545 180209954689 302999489632 849828117651 171771046425 800442975277 295169929534 146003957886
828538 724406 733109 79844 665172 652593...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
1861925516195
1349314434389
1923939896865
1722418218375
1547982260415
1106171281794
1541073508675
1341843630377
1636535366265
1478662771165
1925634723295
1992829328190
1995113361810
1901872214305
1985050672690
1809959812405
1992078880690
1694003671445
188917218...

result:

wrong answer 2nd lines differ - expected: '1384833390877', found: '1861925516195'

Subtask #2:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 253ms
memory: 51276kb

input:

100000
746699125678 374834842799 250803643493 620187038832 454433387570 406226564003 897157438699 99473514061 734784419618 503968957100 363935477037 277126009840 52078020050 990757079812 847235285349 950784717285 271017141367 861087225700 996035427219 520682200664 282013988419 415183977876 882007771...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
1148030742334
1636760433058
2131282232650
2353514637869
2672707119337
2763307672337
2948215735597
3003888852169
3054019822989
3117708941277
3168979051095
3214001638323
3269286229765
3273106480907
3287227043365
3335909595067
3361857042147
3364657567217
338173015...

result:

wrong answer 782nd lines differ - expected: '9624432382807', found: '11712448567744'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 129ms
memory: 47784kb

input:

100000
15175010 23519365 21177669 27079342 9089 16784452 29693960 23124925 17048604 10179491 12828214 24992902 8483134 2928073 23807522 7332137 17421520 28460746 1607282 13224363 11900728 11794692 11495061 4687109 23460275 7657982 27417256 16978162 7326803 23083826 24942987 16610314 12147303 2828271...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
232341708
205703645
186754331
214669009
222056036
224660706
183365807
189869951
232687635
173649777
174706132
166861037
227808734
222377886
177182318
194774237
169590707
203173585
170570274
143738021
230151726
221123879
189011979
233045974
212265735
221947846
1...

result:

wrong answer 2nd lines differ - expected: '16705757', found: '232341708'

Subtask #5:

score: 0
Wrong Answer

Test #94:

score: 0
Wrong Answer
time: 123ms
memory: 46204kb

input:

99281
551670361798 568902251563 418071776626 697635341894 641578820039 117221079324 812766431051 425410617978 663769685693 282144284527 799662290178 749088952784 586626406385 122473825417 459510657357 871705247919 443707710712 735612808044 237919555727 829939639783 122127143240 616906466299 24431898...

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
3044619200677
2727803600038
3064942928013
2781061508799
2870997731892
3059689388168
2653657898526
3067282911716
3130008065557
2618947214891
2544132262152
2910022366508
2755204910605
3130008065557
2910022366508
2692417600050
2743858210721
2960460663568
301831121...

result:

wrong answer 2nd lines differ - expected: '598598746654', found: '3044619200677'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%