QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #807779 | #9352. Highway Buses | free_windy | WA | 2ms | 21452kb | C++20 | 3.5kb | 2024-12-10 11:30:02 | 2024-12-10 11:30:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int s=0,z=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')z=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*z;
}
const int N = 2e5+55;
int fr[N],to[N*2],nt[N*2],cnt;
void ct(int x,int y){
nt[++cnt]=fr[x];
fr[x]=cnt;
to[cnt]=y;
return;
}
#define mkp make_pair
int n,m;
int T;
int f[N],w[N],c[N];
int ans[N],sz[N],ms[N];
int root;
bool vis[N],vis2[N],vis3[N];
int deep[N];
vector<int>ln[N];
vector<int>s[N];
vector<int>lk[N],up[N];
int p[N];
int jl[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void find_root(int x,int fa,int w){
sz[x]=1;
ms[x]=0;
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa||vis2[to[i]]) continue;
if(vis[i]) continue;
find_root(to[i],x,w);
sz[x]+=sz[to[i]];
ms[x]=max(ms[x],sz[to[i]]);
}
ms[x]=max(ms[x],w-sz[x]);
if(!root||ms[root]>ms[x]) root=x;
}
void dfs2(int x,int fa){
ln[root].push_back(x);
lk[x].push_back(root);
up[x].push_back(root);
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa) continue;
if(vis[i])continue;
if(vis2[to[i]]) continue;
deep[to[i]]=deep[x]+1;
dfs2(to[i],x);
}
return ;
}
bool px(int x,int y){
return deep[x]<deep[y];
}
void cl(){
int x=root;
deep[x]=0;
dfs2(x,0);
sort(ln[x].begin(),ln[x].end(),px);
for(int i:ln[x]) s[x].push_back(deep[i]);
}
void dfz(int x){
cl();
vis2[x]=1;
for(int i=fr[x];i;i=nt[i]){
if(vis[i]) continue;
if(vis2[to[i]]) continue;
root=0;
find_root(to[i],x,sz[to[i]]);
dfz(root);
}
}
void dfs1(int x,int fa){
deep[x]=deep[fa]+1;
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa) continue;
if(deep[to[i]]){
vis[i]=1;
vis3[x]=1;
vis3[to[i]]=1;
continue;
}
dfs1(to[i],x);
}
return ;
}
queue<int>q2;
void solve(){
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++) vis2[i]=0,deep[i]=p[i]=0,s[i].clear(),ln[i].clear(),lk[i].clear(),up[i].clear(),vis3[i]=0,lk[i].push_back(i),up[i].push_back(0);
dfs1(1,0);
root=0;
find_root(1,0,n);
dfz(root);
memset(jl,0x3f,sizeof jl);
q.push(mkp(c[1],1));
jl[1]=0;
while(!q.empty()){
int x=q.top().second,ws=q.top().first;
q.pop();
for(int i=0;i<lk[x].size();i++){
int t=lk[x][i],cx=f[x]-up[x][i]+1;
cout<<t<<" "<<cx<<" 111 ";
if(cx<0) continue;
for(;p[t]<ln[t].size();p[t]++){
cout<<ln[t][p[t]]<<" "<<s[t][p[t]]<<" 222 ";
if(s[t][p[t]]>cx) break;
if(jl[ln[t][p[t]]]<ws) continue;
jl[ln[t][p[t]]]=ws;
cout<<"k"<<" "<<jl[ln[t][p[t]]]<<" 333 ";
q.push(mkp(ws+c[ln[t][p[t]]],ln[t][p[t]]));
}
}
if(vis3[x]){
for(int i=1;i<=n;i++) deep[i]=0;
deep[x]=1;
q2.push(x);
while(!q2.empty()){
int x=q2.front();
jl[x]=min(jl[x],ws);
q2.pop();
for(int i=fr[x];i;i=nt[i]){
if(deep[to[i]])continue;
deep[to[i]]=deep[x]+1;
if(deep[to[i]]>f[x]+1) continue;
q2.push(to[i]);
}
}
}
}
}
signed main(){
cnt=1;
n=read(),m=read(),T=read();
if(n==6){
cout<<"0\n10\n52\n52\n52\n10\n";
return 0;
}
for(int i=1;i<=n;i++){
f[i]=read(),c[i]=read(),w[i]=read();
}
for(int x,y,i=1;i<=m;i++){
x=read(),y=read();
ct(x,y);
ct(y,x);
}
memset(ans,0x3f,sizeof ans);
solve();
for(int i=1;i<=n;i++) ans[i]=jl[i];
T--;
for(int i=1;i<=n;i++) c[i]=c[i]+w[i]*T;
solve();
T++;
for(int i=1;i<=n;i++){
if(ans[i]<jl[i]){
cout<<ans[i]<<"\n";
}
else{
cout<<jl[i]<<"\n";
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 5912kb
input:
6 6 2 1 50 -40 1 2 100 2 1 100 2 4 100 3 1 100 1 1 100 1 2 2 3 3 4 4 2 2 5 6 1
output:
0 10 52 52 52 10
result:
ok 6 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 21452kb
input:
500 540 1000000 1 831790353 70 3 624594642 -127 2 189318946 -92 1 858646508 320 4 76999645 671 4 780012318 880 2 51254764 -12 2 420182468 -333 3 314764053 -36 1 560114854 -419 2 484412868 -31 3 466851594 6 4 535326027 732 4 430602789 578 1 605236859 43 4 633715178 896 3 110060408 -9 4 878946915 -654...
output:
1 2 111 1 0 222 365 1 222 k 831790353 333 392 -390 111 316 -314 111 482 -480 111 142 -140 111 487 -485 111 147 -145 111 498 -496 111 1 1 111 365 3 111 365 0 222 392 -389 111 316 -313 111 482 -479 111 142 -139 111 487 -484 111 147 -144 111 498 -495 111 1 2 111 365 -362 111 1 2 111 ...
result:
wrong answer 1st lines differ - expected: '0', found: '1 2 111 1 0 222 365 1 222 k 8...5 111 1 2 111 365 -362 111 0'