QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#100274	#6334. Passport	zhouhuanyi	100 ✓	887ms	293492kb	C++23	3.4kb	2023-04-25 14:08:22	2023-04-25 14:08:43

Judging History

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

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

[2023-04-25 14:08:43]
评测

测评结果：100
用时：887ms
内存：293492kb

查看

[2023-04-25 14:08:22]
提交

answer

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define N 200000
#define M 5000000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct reads
{
    int num,data;
};
int n,q,length,lg[N+1],L[N+1],R[N+1],ST[N+1][21],dis[M+1],dis2[M+1],dis3[M+1],p[N+1];
bool used[M+1];
vector<reads>E[M+1];
void add(int x,int y,int z)
{
    E[x].push_back((reads){y,z});
    return;
}
void add_edge(int x,int l,int r)
{
    int lw=lg[r-l+1];
    add(ST[l][lw],x,1),add(ST[r-(1<<lw)+1][lw],x,1);
    return;
}
void bfs()
{
    int top;
    queue<int>q0;
    queue<int>q1;
    for (int i=1;i<=length;++i) dis[i]=inf,used[i]=0;
    q0.push(1),dis[1]=0;
    while (!q0.empty()||!q1.empty())
    {
	if (!q0.empty()&&(q1.empty()||dis[q0.front()]<dis[q1.front()])) top=q0.front(),q0.pop();
	else top=q1.front(),q1.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis[E[top][i].num]>dis[top]+E[top][i].data)
	    {
		dis[E[top][i].num]=dis[top]+E[top][i].data;
		if (!E[top][i].data) q0.push(E[top][i].num);
		else q1.push(E[top][i].num);
	    }
    }
    return;
}
void bfs2()
{
    int top;
    queue<int>q0;
    queue<int>q1;
    for (int i=1;i<=length;++i) dis2[i]=inf,used[i]=0;
    q0.push(n),dis2[n]=0;
    while (!q0.empty()||!q1.empty())
    {
	if (!q0.empty()&&(q1.empty()||dis2[q0.front()]<dis2[q1.front()])) top=q0.front(),q0.pop();
	else top=q1.front(),q1.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis2[E[top][i].num]>dis2[top]+E[top][i].data)
	    {
		dis2[E[top][i].num]=dis2[top]+E[top][i].data;
		if (!E[top][i].data) q0.push(E[top][i].num);
		else q1.push(E[top][i].num);
	    }
    }
    return;
}
bool cmp(int x,int y)
{
    return dis3[x]<dis3[y];
}
void dijkstra()
{
    int top;
    queue<int>q0;
    queue<int>q1;
    queue<int>q2;
    for (int i=1;i<=length;++i)
    {
	dis3[i]=inf,used[i]=0;
	if (i<=n) dis3[i]=min(dis3[i],max(dis[i]-1,0)+max(dis2[i]-1,0)+1);
    }
    for (int i=1;i<=n;++i) p[i]=i;
    sort(p+1,p+n+1,cmp);
    for (int i=1;i<=n;++i) q2.push(p[i]);
    while (!q0.empty()||!q1.empty()||!q2.empty())
    {
	if (!q0.empty()&&(q1.empty()||dis3[q0.front()]<dis3[q1.front()])&&(q2.empty()||dis3[q0.front()]<dis3[q2.front()])) top=q0.front(),q0.pop();
	else if (!q1.empty()&&(q2.empty()||dis3[q1.front()]<dis3[q2.front()])) top=q1.front(),q1.pop();
	else top=q2.front(),q2.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis3[E[top][i].num]>dis3[top]+E[top][i].data)
	    {
		dis3[E[top][i].num]=dis3[top]+E[top][i].data;
		if (!E[top][i].data) q0.push(E[top][i].num);
		else q1.push(E[top][i].num);
	    }
    }
    return;
}
int main()
{
    int x;
    for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
    length=n=read();
    for (int i=1;i<=n;++i) L[i]=read(),R[i]=read(),ST[i][0]=i;
    for (int i=1;i<=lg[n];++i)
	for (int j=1;j+(1<<i)-1<=n;++j)
	    ST[j][i]=++length,add(ST[j][i-1],ST[j][i],0),add(ST[j+(1<<(i-1))][i-1],ST[j][i],0);
    for (int i=1;i<=n;++i) add_edge(i,L[i],R[i]);
    bfs(),bfs2(),dijkstra(),q=read();
    while (q--)
    {
	x=read();
	if (dis3[x]>n) puts("-1");
	else printf("%d\n",dis3[x]);
    }
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 29ms

memory: 121368kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 20ms

memory: 121572kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 878ms

memory: 292536kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 659ms

memory: 291860kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 860ms

memory: 288832kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 381ms

memory: 283884kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 263ms

memory: 249324kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 27ms

memory: 121576kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 28ms

memory: 121384kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 27ms

memory: 121560kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 25ms

memory: 121572kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 25ms

memory: 121636kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 19ms

memory: 121576kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 31ms

memory: 121708kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 24ms

memory: 121728kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 20ms

memory: 121696kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 24ms

memory: 121732kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 33ms

memory: 121772kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 27ms

memory: 122920kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 21ms

memory: 123032kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 39ms

memory: 123016kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 30ms

memory: 122972kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 26ms

memory: 122980kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 28ms

memory: 123052kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 24ms

memory: 122856kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 33ms

memory: 123092kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 31ms

memory: 123100kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 32ms

memory: 122992kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 20ms

memory: 123052kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 18ms

memory: 123084kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 32ms

memory: 123004kb

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: 23ms

memory: 123012kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 887ms

memory: 293492kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 709ms

memory: 293480kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 670ms

memory: 292128kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 640ms

memory: 292260kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 872ms

memory: 288936kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 853ms

memory: 290312kb

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: 198ms

memory: 180292kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 475ms

memory: 291948kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 512ms

memory: 289776kb

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