QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105990 | #6101. Ring Road | 1kri | RE | 5ms | 18680kb | C++14 | 4.6kb | 2023-05-16 10:12:30 | 2023-05-16 10:12:32 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
const ll inf=1000000000000000000ll;
void updmin(ll &x,ll y){
if (y<x)x=y;
return;
}
int _abs(int x){
if (x<0)return -x;
return x;
}
int n,q;
vector<int> e[200005];
vector<ll> ew[200005];
int m,u[400005],v[400005],first[200005],nxt[400005];
ll w[400005];
void add_edge(int a,int b,ll c){
int i=++m;
u[i]=a,v[i]=b,w[i]=c;
nxt[i]=first[u[i]],first[u[i]]=i;
i=++m;
u[i]=b,v[i]=a,w[i]=c;
nxt[i]=first[u[i]],first[u[i]]=i;
return;
}
int tot,c[200005];
void build(int now){
if (e[now].size()==0)c[++tot]=now;
else{
int t=now;
for (int i=0;i<(int)e[now].size();i++){
++n;
add_edge(t,n,0);
add_edge(n,e[now][i],ew[now][i]);
t=n;
}
for (int i=0;i<(int)e[now].size();i++)build(e[now][i]);
}
return;
}
int a[300005],b[300005];
vector<int> qid[200005];
ll ans[300005];
struct Edge{
int u,v;
ll w;
};
Edge make_Edge(int u,int v,ll w){
Edge ans;
ans.u=u,ans.v=v,ans.w=w;
return ans;
}
namespace Graph{
vector<int> id;
vector<Edge> e;
int m,u[400005],v[400005],first[200005],nxt[400005];
ll w[400005];
void add_edge(int a,int b,ll c){
int i=++m;
u[i]=a,v[i]=b,w[i]=c;
nxt[i]=first[u[i]],first[u[i]]=i;
i=++m;
u[i]=b,v[i]=a,w[i]=c;
nxt[i]=first[u[i]],first[u[i]]=i;
return;
}
struct node{
int id;
ll dis;
bool operator <(const node &y)const{
return y.dis<dis;
}
};
node make_node(int id,ll dis){
node ans;
ans.id=id,ans.dis=dis;
return ans;
}
priority_queue<node> h;
int book[200005];
ll dis[200005];
void build(vector<int> _id,vector<Edge> _e){
id=_id,e=_e;
for (int i=0;i<(int)e.size();i++)add_edge(e[i].u,e[i].v,e[i].w);
return;
}
void upd(Edge x){
for (int i=0;i<(int)id.size();i++)book[id[i]]=0,dis[id[i]]=inf;
dis[x.u]=dis[x.v]=0;
h.push(make_node(x.u,0));
h.push(make_node(x.v,0));
while(!h.empty()){
int now=(h.top()).id;
h.pop();
if (book[now]==1)continue;
book[now]=1;
for (int i=first[now];i;i=nxt[i])
if (dis[v[i]]>dis[now]+w[i]){
dis[v[i]]=dis[now]+w[i];
h.push(make_node(v[i],dis[v[i]]));
}
}
for (int i=0;i<(int)id.size();i++)book[id[i]]=1;
for (int i=0;i<(int)id.size();i++)
for (int j=0;j<(int)qid[id[i]].size();j++){
int t=qid[id[i]][j];
if (book[a[t]]==1&&book[b[t]]==1)updmin(ans[t],dis[a[t]]+x.w+dis[b[t]]);
}
return;
}
void clear(){
while(m>0){
nxt[m]=first[u[m]]=0;
u[m]=v[m]=w[m]=0;
m--;
}
for (int i=0;i<(int)id.size();i++)book[id[i]]=0;
id.clear();
e.clear();
return;
}
}
int book[200005];
int sum_n,fa[200005],sz[200005],rt;
void find_rt(int now,int f){
fa[now]=f;
sz[now]=1;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=f&&book[v[i]]==1){
find_rt(v[i],now);
sz[now]+=sz[v[i]];
}
if (rt==0||_abs(2*sz[now]-sum_n)<=_abs(2*sz[rt]-sum_n))rt=now;
return;
}
int col[200005];
void get_col(int now,int f){
col[now]=1;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=f&&book[v[i]]==1)get_col(v[i],now);
return;
}
void work(vector<int> id,vector<Edge> e){
if ((int)id.size()==1)return;
for (int i=0;i<(int)id.size();i++)book[id[i]]=1;
sum_n=(int)id.size(),rt=0;
find_rt(id[0],0);
int x=rt,y=fa[rt];
get_col(x,y);
vector<Edge> _e=e;
for (int i=0;i<(int)id.size();i++)
for (int j=first[id[i]];j;j=nxt[j])
if (book[v[j]]==1&&v[j]!=fa[u[j]])_e.push_back(make_Edge(u[j],v[j],w[j]));
Graph::build(id,_e);
vector<int> id_x,id_y;
vector<Edge> e_x,e_y;
for (int i=0;i<(int)id.size();i++)
if (col[id[i]]==1)id_x.push_back(id[i]);
else id_y.push_back(id[i]);
for (int i=0;i<(int)e.size();i++)
if (col[e[i].u]==1&&col[e[i].v]==1)e_x.push_back(e[i]);
else if (col[e[i].u]==0&&col[e[i].v]==0)e_y.push_back(e[i]);
else Graph::upd(e[i]);
for (int i=first[x];i;i=nxt[i])
if (v[i]==y)Graph::upd(make_Edge(u[i],v[i],w[i]));
for (int i=0;i<(int)id.size();i++)book[id[i]]=col[id[i]]=0;
Graph::clear();
work(id_x,e_x);
work(id_y,e_y);
return;
}
int main(){
cin>>n;
for (int i=2;i<=n;i++){
int p;
ll c;
scanf("%d%lld",&p,&c);
e[p].push_back(i);
ew[p].push_back(c);
}
build(1);
vector<int> id;
vector<Edge> qwq;
for (int i=1;i<=n;i++)id.push_back(i);
for (int i=1;i<=tot;i++){
ll x;
scanf("%lld",&x);
qwq.push_back(make_Edge(c[i],c[i%tot+1],x));
}
cin>>q;
for (int i=1;i<=q;i++){
scanf("%d%d",&a[i],&b[i]);
qid[a[i]].push_back(i);
qid[b[i]].push_back(i);
ans[i]=inf;
}
if (n>11451)q=0;
work(id,qwq);
for (int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 18572kb
input:
4 1 9 1 8 1 0 9 9 9 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
9 8 0 9 9 8
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 5ms
memory: 18680kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 0 0 0 0 0 0 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
7 8 8 7 7 7 0 7 1 7 7 7 1 7 0 7 0 8 1 6 0
result:
ok 21 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 18500kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
9 8 8 15 9 14 0 7 1 7 14 9 15 9 22 9 23 8 15 16 16
result:
ok 21 numbers
Test #4:
score: -100
Runtime Error
input:
99998 1 683940 1 335116 3 198362 4 28825 5 625394 6 314200 7 270653 8 61629 9 650997 10 693039 11 159577 12 466708 13 715788 14 262771 15 615302 16 1457 17 650381 18 542652 19 101993 20 197937 21 474452 22 859631 23 327526 24 705522 25 500710 26 595050 27 577264 28 955258 29 269967 30 4012 31 471435...