QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#785009 | #6660. 택시 여행 | ktq_cpp | 0 | 187ms | 41420kb | C++14 | 4.3kb | 2024-11-26 16:35:13 | 2024-11-26 16:35:14 |
Judging History
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 1.*(y.y-x.y)*(z.x-y.x)>1.*(z.y-y.y)*(y.x-x.x);
}
bool check(Point x,Point y,ll k){
return 1.*(y.y-x.y)>1.*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);
return;
}
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]<<' '<<check(stk[1],stk[2],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;
while(x){
mn=min(mn,L[x].query(get_dis(u,x)));
x=Fa[x];
}
return mn;
}
void add(int u,ll X,ll Y){
int x=u;
while(x){
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+(1<<j)-1<=n;i++){
mi[j][i]=get(mi[j-1][i],mi[j-1][i+(1<<j-1)]);
}
}
for(int i=2;i<=n;i++)dp[i]=inf;
bool flag=0;
for(int i=1;i<=n;i++){
if(a[i].id!=1)dp[a[i].id]=PointmasTree::solve(a[i].id);
else flag=1;
if(flag)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
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 2ms
memory: 12480kb
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: 3ms
memory: 14292kb
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: 16184kb
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: 14252kb
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: 11008kb
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: 14756kb
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: 17760kb
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: 2ms
memory: 13400kb
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: 0ms
memory: 15108kb
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: 7
Accepted
time: 2ms
memory: 16216kb
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 1384833390877 871900130923 1446847771547 1245326093057 924349900475 1046486123707 1063981383357 864751505059 1159443240947 824076089025 1448542597977 1486181926466 1488465960086 1424780088987 1478403270966 1303312410681 1485431478966 1135576549657 1412080059777...
result:
ok 21 lines
Test #11:
score: 7
Accepted
time: 0ms
memory: 12988kb
input:
20 286866076510 666296858783 319893290745 436172872006 579306725182 388780143357 429085643976 163864091991 334402956892 573150791451 971047548996 924353133556 82495144441 364862686518 76783079529 74022380610 978776791995 17833817791 637808249822 150520055702 705613 111460 694926 702547 748042 671482...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1345583882860 995125125260 815198043938 1295987956432 1034264067144 888082221934 1247814963646 1225117709350 631676569994 1289347270738 404306893004 1347095564962 373415155864 1441975557454 1167058795516 1091947224281 1373264198836 795244013911 1127743556434 se...
result:
ok 21 lines
Test #12:
score: 7
Accepted
time: 3ms
memory: 15244kb
input:
20 161996998737 15089127085 28063038428 574601167323 736141386895 762192247356 788118187801 956063872362 580983462657 839554694910 471536078792 781164874294 363054673222 809510755913 153755418459 78171544930 969593469579 864779185396 408120998971 610129629325 933618 563940 506188 824442 64614 396381...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1870873819056 1340292002469 2180029603234 1667979150565 2084831816447 1131232525437 1898452835615 1742994070672 2139665843266 1042857179175 2148449164384 1856727805178 2077059488718 1931794896836 1753987714167 1864830429393 1705470391803 1529058594761 197326523...
result:
ok 21 lines
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 16192kb
input:
20 443174843835 295023765677 175861678382 805210665445 724299682774 889923334441 967560897715 857729286838 7238459275 901083586058 887820756720 681912091803 886476957360 821901344613 222491154905 602669810322 953890359316 822857333786 674877086360 498973934687 505612 0 0 0 913180 49780 0 0 0 0 0 0 0...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1404583673007 737522649521 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 1404583673007 7375226495...
result:
wrong answer 2nd lines differ - expected: '737522649521', found: '1404583673007'
Subtask #2:
score: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 187ms
memory: 41420kb
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 17475483844606 17445426755181 17415013448531 17397943377806 17368146998781 17359689505031 17328373514081 17300760807431 17275896889681 17244308413081 17218879506106 17196549240256 17169129233981 17167234468956 17160230963981 17136085431956 17123216038456 171218...
result:
wrong answer 2nd lines differ - expected: '1148030742334', found: '17475483844606'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 0
Wrong Answer
time: 75ms
memory: 32644kb
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 95925210 95925210 95925210 95925210 95925210 64824740 95925210 95925210 95925210 79298855 95925210 81243558 95925210 95925210 95925210 72897034 95925210 95925210 92125817 95925210 95925210 95925210 95925210 95925210 95925210 95925210 91063039 95925210 95925210 ...
result:
wrong answer 2nd lines differ - expected: '16705757', found: '95925210'
Subtask #5:
score: 0
Wrong Answer
Test #94:
score: 0
Wrong Answer
time: 119ms
memory: 37608kb
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 1564895382674 1354643328052 1496344518527 1206909931381 1430010216014 1752470525764 1265314904847 1373980442704 1473656397565 1420837170476 1752470525764 1101347887843 1269597823982 1381381208308 1301194076495 1536588118776 1682651836970 1458077140302 123631668...
result:
wrong answer 2nd lines differ - expected: '598598746654', found: '1564895382674'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%