QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#111603	#6334. Passport	Flamire	100 ✓	855ms	70500kb	C++14	1.6kb	2023-06-07 17:35:31	2023-06-07 17:35:32

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-07 17:35:32]
评测

测评结果：100
用时：855ms
内存：70500kb

查看

[2023-06-07 17:35:31]
提交

answer

#include <bits/stdc++.h>
#define N 200011
using namespace std;
int n,l[N],r[N],lc[N*4],rc[N*4],nd,q,ans[N*4],rt;
struct edge{int v,w,next;edge(){}edge(int _v,int _w,int _next){v=_v;w=_w;next=_next;}}e[N*50];int head[N*4],sz;
void init(){memset(head,-1,sizeof(head));sz=0;}void insert(int u,int v,int w){e[++sz]=edge(v,w,head[u]);head[u]=sz;}
void build(int l,int r,int &x)
{
	if(l==r){x=l;return;}
	if(!x)x=++nd;build(l,l+r>>1,lc[x]);build((l+r>>1)+1,r,rc[x]);insert(lc[x],x,0);insert(rc[x],x,0);
}
void adde(int l,int r,int v,int w,int L,int R,int x)
{
	if(l<=L&&R<=r){insert(x,v,w);return;}
	if(l<=L+R>>1)adde(l,r,v,w,L,L+R>>1,lc[x]);if(r>L+R>>1)adde(l,r,v,w,(L+R>>1)+1,R,rc[x]);
}
struct node{int v,d;node(){}node(int _v,int _d){v=_v;d=_d;}};
bool operator<(node a,node b){return a.d>b.d;}
bool vis[N*4];int disa[N*4],disb[N*4];
void dijk(int s,int *dis)
{
	priority_queue<node> pq;pq.push(node(s,0));
	for(int i=1;i<=nd;++i)vis[i]=0,dis[i]=1e9;dis[s]=0;
	while(!pq.empty())
	{
		int p=pq.top().v;pq.pop();if(vis[p])continue;vis[p]=1;
		for(int i=head[p];~i;i=e[i].next)if(dis[e[i].v]>dis[p]+e[i].w)
		{
			dis[e[i].v]=dis[p]+e[i].w;pq.push(node(e[i].v,dis[e[i].v]));
		}
	}
}
int main()
{
	scanf("%d",&n);init();for(int i=1;i<=n;++i)scanf("%d%d",l+i,r+i);
	nd=n+3;build(1,n,rt);
	for(int i=1;i<=n;++i)
	{
		if(l[i]==1)insert(n+1,i,0);if(r[i]==n)insert(n+2,i,0);
		adde(l[i],r[i],i,1,1,n,rt);
	}
	dijk(n+1,disa);dijk(n+2,disb);
	for(int i=1;i<=n;++i)insert(n+3,i,min(disa[i]+disb[i],1000000000));
	dijk(n+3,ans);
	scanf("%d",&q);while(q--)
	{
		int x;scanf("%d",&x);if(ans[x]>n)printf("-1\n");else printf("%d\n",ans[x]+1);
	}return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 2ms

memory: 18020kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 1ms

memory: 15980kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 799ms

memory: 65288kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 150ms

memory: 42304kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 67ms

memory: 37952kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 89ms

memory: 41500kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 79ms

memory: 48492kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 1ms

memory: 16000kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 2ms

memory: 15980kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 2ms

memory: 14012kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 3ms

memory: 16024kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 2ms

memory: 16000kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 2ms

memory: 15948kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 2ms

memory: 15968kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 1ms

memory: 13948kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 2ms

memory: 13996kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 2ms

memory: 16020kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 2ms

memory: 13948kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 2ms

memory: 16024kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 2ms

memory: 16068kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 1ms

memory: 16076kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 7ms

memory: 16120kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 1ms

memory: 16072kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 3ms

memory: 16056kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 1ms

memory: 16032kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 7ms

memory: 16076kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 3ms

memory: 16052kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 4ms

memory: 16080kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 3ms

memory: 14060kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 2ms

memory: 14056kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 7ms

memory: 14020kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2500 lines

Test #32:

score: 0

Accepted

time: 4ms

memory: 16136kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 855ms

memory: 68084kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 174ms

memory: 42068kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 331ms

memory: 69136kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 333ms

memory: 70500kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 107ms

memory: 37280kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 133ms

memory: 45100kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #39:

score: 0

Accepted

time: 70ms

memory: 24656kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 301ms

memory: 47728kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 154ms

memory: 53568kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 199636 lines

Extra Test:

score: 0

Extra Test Passed