QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784831 | #6660. 택시 여행 | ktq_cpp | 0 | 242ms | 43896kb | C++14 | 4.5kb | 2024-11-26 16:04:31 | 2024-11-26 16:04:31 |
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 (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
详细
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%