提交记录 12855


用户 题目 状态 得分 用时 内存 语言 代码长度
luosiyuan noi18a. 【NOI2018】归程 Accepted 100 1.235 s 72 MB + 592 KB C++11 2.41 KB
提交时间 评测时间
2020-06-13 19:41:51 2020-08-01 03:00:15
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
struct Edge {
	int to,next,value,height;
} e[800005],e3[800005];
struct Edge2 {
	int from,to,height;
	bool operator <(const Edge2 xx) const {
		return height>xx.height;
	}
} e2[400005];
struct Node {
	int num,dis;
	bool operator <(const Node xx) const {
		return dis>xx.dis;
	}
};
int n,m,q,K,S,h[400005],prt[400005],cnt,dis[400005],cnt3,h3[400005],p[400005][20],mindis[400005],val[400005];
void Add_Edge(int x,int y,int z,int w) {
	e[++cnt]=(Edge){y,h[x],z,w};
	h[x]=cnt;
}
void Add_Edge3(int x,int y) {
	e3[++cnt3]=(Edge){y,h3[x],0,0};
	h3[x]=cnt3;
}
void Dijkstra(int from) {
	priority_queue<Node> q;
	q.push((Node){from,0});
	for(int i=1; i<=n; i++)dis[i]=0x7fffffff;
	dis[from]=0;
	while(!q.empty()) {
		Node nnow=q.top();
		q.pop();
		if(dis[nnow.num]!=nnow.dis)continue;
		int now=nnow.num;
		for(int i=h[now]; i; i=e[i].next) {
			int y=e[i].to;
			if(dis[now]+e[i].value<dis[y]) {
				dis[y]=dis[now]+e[i].value;
				q.push((Node){y,dis[y]});
			}
		}
	}
}
int Getfa(int x) {
	return x==prt[x]?x:prt[x]=Getfa(prt[x]);
}
void MakeKruskal() {
	sort(e2+1,e2+m+1);
	for(int i=1; i<=n; i++)prt[i]=i;
	for(int i=1,tot=n; i<=m; i++) {
		int fx=Getfa(e2[i].from),fy=Getfa(e2[i].to);
		if(fx==fy)continue;
		prt[fx]=prt[fy]=++tot,prt[tot]=tot,val[tot]=e2[i].height;
		Add_Edge3(tot,fx);
		Add_Edge3(tot,fy);
	}
}
void DFS(int now,int fa) {
	p[now][0]=fa;
	for(int i=1; p[now][i-1]; i++)p[now][i]=p[p[now][i-1]][i-1];
	if(now<=n)mindis[now]=dis[now];
	else mindis[now]=0x7fffffff;
	for(int i=h3[now]; i; i=e3[i].next) {
		int y=e3[i].to;
		if(y==fa)continue;
		DFS(y,now);
		mindis[now]=min(mindis[now],mindis[y]);
	}
}
int main() {
//	freopen("testdata.in","r",stdin);
//	freopen("a.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--) {
		memset(h,0,sizeof(h));
		memset(h3,0,sizeof(h3));
		memset(val,0,sizeof(val));
		memset(p,0,sizeof(p));
		cnt=cnt3=0;
		scanf("%d%d",&n,&m);
		for(int i=1,x,y,z,w; i<=m; i++) {
			scanf("%d%d%d%d",&x,&y,&z,&w);
			Add_Edge(x,y,z,w),Add_Edge(y,x,z,w);
			e2[i]=(Edge2){x,y,w};
		}
		Dijkstra(1);
		MakeKruskal();
		DFS(2*n-1,0);
		scanf("%d%d%d",&q,&K,&S);
		for(int i=1,lastans=0,v,pp,md=log2(n); i<=q; i++) {
			scanf("%d%d",&v,&pp);
			v=(v+lastans*K-1)%n+1,pp=(pp+lastans*K)%(S+1);
			for(int j=md; j>=0; j--)if(val[p[v][j]]>pp)v=p[v][j];
			printf("%d\n",lastans=mindis[v]);
		}
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #15.483 ms35 MB + 140 KBAcceptedScore: 5

Testcase #25.522 ms35 MB + 152 KBAcceptedScore: 5

Testcase #35.668 ms35 MB + 172 KBAcceptedScore: 5

Testcase #45.813 ms35 MB + 176 KBAcceptedScore: 5

Testcase #59.407 ms35 MB + 448 KBAcceptedScore: 5

Testcase #6601.57 ms64 MB + 644 KBAcceptedScore: 5

Testcase #78.528 ms35 MB + 368 KBAcceptedScore: 5

Testcase #88.524 ms35 MB + 376 KBAcceptedScore: 5

Testcase #98.527 ms35 MB + 372 KBAcceptedScore: 5

Testcase #10456.946 ms57 MB + 856 KBAcceptedScore: 5

Testcase #11457.435 ms57 MB + 864 KBAcceptedScore: 5

Testcase #12685.204 ms69 MB + 100 KBAcceptedScore: 5

Testcase #13684.678 ms69 MB + 104 KBAcceptedScore: 5

Testcase #14684.873 ms69 MB + 128 KBAcceptedScore: 5

Testcase #159.845 ms35 MB + 472 KBAcceptedScore: 5

Testcase #169.858 ms35 MB + 476 KBAcceptedScore: 5

Testcase #17685.031 ms69 MB + 104 KBAcceptedScore: 5

Testcase #18685.014 ms69 MB + 100 KBAcceptedScore: 5

Testcase #191.23 s72 MB + 572 KBAcceptedScore: 5

Testcase #201.235 s72 MB + 592 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2020-08-14 12:41:40 | Loaded in 23 ms | Server Status
个人娱乐项目,仅供学习交流使用