QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#784831#6660. 택시 여행ktq_cpp0 242ms43896kbC++144.5kb2024-11-26 16:04:312024-11-26 16:04:31

Judging History

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

  • [2024-11-26 16:04:31]
  • 评测
  • 测评结果:0
  • 用时:242ms
  • 内存:43896kb
  • [2024-11-26 16:04:31]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int N=1e5+5;
const ll inf=5e18;
struct Car{
	ll x;
	int y,id;
}a[N];
vector<pair<int,int>> G[N];
bool vis[N];
int sz[N],mx[N],all,rt;
int dep[N];
ll dis[N];
int dfn[N],mi[20][N],rnk[N],dfncnt;
int Fa[N];
int get(int x,int y){
	return dfn[x]<dfn[y]? x:y;
}
void init(int u,int fa){
	dep[u]=dep[fa]+1;
	mi[0][dfn[u]=++dfncnt]=fa;
	for(auto ed:G[u]){
		int v=ed.first,w=ed.second;
		if(v==fa)continue;
		dis[v]=dis[u]+w;
		init(v,u);
	}
	return;
}
void calc(int u,int fa){
	sz[u]=1,mx[u]=0;
	for(auto ed:G[u]){
		int v=ed.first;
		if(v==fa||vis[v])continue;
		calc(v,u);
		mx[u]=max(mx[u],sz[v]);
		sz[u]+=sz[v];
	}
	mx[u]=max(mx[u],all-sz[u]);
	if(!rt||mx[rt]>mx[u])rt=u;
	return;
}
void dfs(int u,int fa){
	Fa[u]=fa;
	vis[u]=1;
//	cout<<u<<' '<<fa<<endl;
	for(auto ed:G[u]){
		int v=ed.first;
		if(v==fa||vis[v])continue;
		rt=0;
		all=sz[v];
		calc(v,u);
		calc(rt,u);
		dfs(rt,u);
	}
	return;
}
ll dp[N];
struct Point{
	ll x,y;
	ll operator[](ll k){
		return y-x*k;
	}
};
struct LINE{
	vector<Point> stk;
	bool check(Point x,Point y,Point z){
		return (y.y-x.y)*(z.x-y.x)>(z.y-y.y)*(y.x-x.x);
	}
	bool check(Point x,Point y,ll k){
		return (y.y-x.y)>k*(y.x-x.x);
	}
	void add(Point x){
		//cout<<x.x<<' '<<x.y<<endl;
		int top=(int)stk.size();
		while((int)top>=2&&check(stk[top-2],stk[top-1],x)){
			--top;stk.pop_back();
		}
		stk.push_back(x);
	}
	ll query(ll k){
		if(stk.empty())return inf;
		int l=0,r=(int)stk.size()-2,res=(int)stk.size()-1;
		while(l<=r){
			int mid=l+r>>1;
			if(check(stk[mid],stk[mid+1],k))r=mid-1,res=mid;
			else l=mid+1;
		}
//		cout<<k<<' '<<res<<' '<<' '<<stk[res].x<<' '<<stk[res].y<<' '<<stk[res][k]<<'\n';
		return stk[res][k];
	}
}L[N];
int lca(int u,int v){
	if(u==v)return u;
	u=dfn[u],v=dfn[v];
	if(u>v)swap(u,v);
	int len=__lg(v-u++);
	return get(mi[len][u],mi[len][v-(1<<len)+1]);
}
ll get_dis(int x,int y){
	return dis[x]+dis[y]-dis[lca(x,y)]*2;
}
namespace PointmasTree{
	ll solve(int u){
		ll mn=inf;
		int x=u;
//		cout<<"u=="<<u<<endl;
		while(x){
//			cout<<"x=="<<x<<endl;
			mn=min(mn,L[x].query(get_dis(u,x)));
//			cout<<x<<" "<<L[x].query(get_dis(u,x))<<endl;
			x=Fa[x];
		}
		return mn;
	}
	void add(int u,ll X,ll Y){
		int x=u;
//		cout<<"add u=="<<u<<endl;
		while(x){
//			cout<<"x=="<<x<<endl;
//			cout<<dp[u]<<' '<<X<<' '<<Y<<' '<<get_dis(u,x)<<endl;
			L[x].add({-Y,dp[u]+X+Y*get_dis(u,x)});
			x=Fa[x];
		}
		return;
	}
}
vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U,vector<int> V, vector<int> W){
	n=(int)A.size();
	for(int i=1;i<=n;i++){
		a[i].x=A[i-1],a[i].y=B[i-1],a[i].id=i;
	}
	sort(a+1,a+n+1,[&](Car a,Car b){
		return a.y>b.y;
	});
	for(int i=0;i<n-1;i++){
		G[U[i]+1].push_back({V[i]+1,W[i]});
		G[V[i]+1].push_back({U[i]+1,W[i]});
	}
	all=n,rt=0;
	init(1,0);
	calc(1,0);
	dfs(1,0);
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n;i++){
			mi[j][i]=get(mi[j-1][i],mi[j-1][i+(1<<j-1)]);
		}
	}
//	cout<<lca(5,3)<<' '<<get_dis(5,3)<<endl;
	for(int i=2;i<=n;i++)dp[i]=inf;
	for(int i=1;i<=n;i++){
		if(a[i].id!=1)dp[a[i].id]=PointmasTree::solve(a[i].id);
		PointmasTree::add(a[i].id,a[i].x,a[i].y);
	}
//	cout<<'\n';
//	for(int i=1;i<=n;i++){
//		cout<<dp[i]<<' ';
//	}
//	cout<<'\n';
	vector<ll> ans;
	ans.resize(n-1,0);
	for(int i=2;i<=n;i++){
		ans[i-2]=PointmasTree::solve(i);
	}
	return ans;
}
#ifndef ONLINE_JUDGE
signed main(){
	int NN;
	scanf("%d",&NN);
	vector<ll> A;
	vector<int> B,U,V,W;
	for(int i=1;i<=NN;i++){
		ll x;
		scanf("%lld",&x);
		A.push_back(x);
	}
	for(int i=1;i<=NN;i++){
		int x;
		scanf("%d",&x);
		B.push_back(x);
	}
	for(int i=1,u,v,w;i<NN;i++){
		scanf("%d %d %d",&u,&v,&w);
		U.push_back(u);
		V.push_back(v);
		W.push_back(w);
	}
	vector<ll> ans=travel(A,B,U,V,W);
	for(int i=0;i<NN-1;i++)printf("%lld\n",ans[i]);
	return 0;
}
/*
input:
5
10 5 13 4 3
10 7 5 9 1
1 0 1
0 2 5
3 2 10
2 4 3

output:
20
60
104
88
*/
/*
input:
10
422984347234 607725142104 92118155366 486587956717 857158857503 799145939144 657596100723 796939845406 986487843217 23702497547
410761 491391 858697 690385 801672 657901 640039 950942 514882 665242
0 1 736069
1 2 871348
2 3 300958
3 4 249899
4 5 977539
5 6 867002
6 7 648549
7 8 891403
8 9 132040

output:
725332785743
1083248561571
1206870370609
1309519133748
1711054030927
2067184639449
2333583275238
2699736862921
2753973745361
*/
#endif

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 13124kb

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: 0ms
memory: 17568kb

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: 2ms
memory: 16492kb

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: 2ms
memory: 13256kb

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: 0
Wrong Answer
time: 0ms
memory: 11116kb

input:

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

output:

secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
990561996130
2072458437031
2081105045883
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I

result:

wrong answer 2nd lines differ - expected: '830324131649', found: '990561996130'

Subtask #2:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 242ms
memory: 43896kb

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
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5...

result:

wrong answer 2nd lines differ - expected: '1148030742334', found: '5000000000000000000'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 102ms
memory: 38088kb

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
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5...

result:

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

Subtask #5:

score: 0
Wrong Answer

Test #94:

score: 0
Wrong Answer
time: 102ms
memory: 38720kb

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
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5000000000000000000
5...

result:

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

Subtask #6:

score: 0
Skipped

Dependency #1:

0%