QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#218616#6101. Ring Road275307894aWA 0ms40844kbC++142.8kb2023-10-18 15:53:502023-10-18 15:53:51

Judging History

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

  • [2023-10-18 15:53:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:40844kb
  • [2023-10-18 15:53:50]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__uint128_t;
const int N=3e5+5,M=N*8+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,fa[N];ll w[N];vector<pair<int,ll> > S[N];vector<int> G[N],son[N];
vector<pii> q[N];ll ans[N];
void con(int x,int y){S[x].eb(y,w[y]);S[y].eb(x,w[y]);G[x].eb(y);G[y].eb(x);}
void reb(vector<int> son,int x){
	if(son.empty()) return;
	if(son.size()==1) {con(x,son.back());return;}
	int v=++m,Le=son.size()/2;con(x,v);
	vector<int> ls(son.begin(),son.begin()+Le),rs(son.begin()+Le,son.end());
	reb(ls,m);reb(rs,m);
}
int Ct,f[N],siz[N],vis[N],col[N],Rt;
ll d[N];
vector<int> scc;
void dij(int x){
	for(int i:scc) d[i]=1e18;d[x]=0;
	priority_queue<pair<ll,int> > Q;Q.emplace(0,x);
	while(!Q.empty()){
		auto p=Q.top();Q.pop();p.fi*=-1;if(p.fi^d[p.se]) continue;
		for(auto i:S[p.se]) if(d[i.fi]>i.se+p.fi) d[i.fi]=i.se+p.fi,Q.emplace(-d[i.fi],i.fi);
	}
	for(int i:scc) for(auto j:q[i]) if(col[j.fi]==col[i]) ans[j.se]=min(ans[j.se],d[i]+d[j.fi]);
}
void GI(int x,int La){scc.eb(x);siz[x]=1;col[x]=Rt;for(int i:G[x]) if(i^La&&!vis[i]) GI(i,x),siz[x]+=siz[i];}
void DP(int x,int La){f[x]=Ct-siz[x];for(int i:G[x]) if(i^La&&!vis[i]) f[x]=max(f[x],siz[i]),DP(i,x);if(f[Rt]>f[x]) Rt=x;}
pii search(int x,int La){
	if(son[x].empty()&&x<=n) return make_pair(x,x); 
	pii ans=make_pair(INF,-INF);
	for(int i:G[x]) if(!vis[i]&&i^La) {auto p=search(i,x);ans.fi=min(ans.fi,p.fi);ans.se=max(ans.se,p.se);}
	return ans;
}
void dfs(int x){
	scc.clear();Rt=x;GI(x,0);Ct=siz[x];f[Rt=0]=INF;DP(x,0);vis[x=Rt]=1;if(clock()*1.0/CLOCKS_PER_SEC>2.5) return;
	dij(x);assert(G[x].size()<=3);
	for(int i:G[x]) if(!vis[i]) {
		auto p=search(i,x);
		if(p.fi<=n) dij(p.fi);
		if(p.se>p.fi) dij(p.se);
	}
	for(int i:G[x]) if(!vis[i]) dfs(i);
}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=2;i<=n;i++) scanf("%d%lld",&fa[i],&w[i]),son[fa[i]].eb(i);
	m=n;for(i=1;i<=n;i++) reb(son[i],i);
	vector<int> leaf;
	for(i=1;i<=n;i++) if(son[i].empty()) leaf.eb(i);leaf.eb(leaf.front());
	for(i=1;i<leaf.size();i++) {ll y;scanf("%lld",&y);S[leaf[i]].eb(leaf[i-1],y);S[leaf[i-1]].eb(leaf[i],y);}
	int Q;scanf("%d",&Q);for(i=1;i<=Q;i++){int x,y;scanf("%d%d",&x,&y);q[x].eb(y,i);q[y].eb(x,i);ans[i]=1e18;}
	dfs(1);for(i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 34720kb

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

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
1
1
0
0
0
0
0
1
0
0
7
1
7
0
0
0
8
1
6
0

result:

wrong answer 2nd numbers differ - expected: '8', found: '1'