QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235387 | #6334. Passport | 275307894a | 0 | 28ms | 5860kb | C++14 | 1.2kb | 2023-11-02 18:32:11 | 2023-11-02 18:32:11 |
Judging History
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=__int128;
const int N=2e5+5,M=5e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,L[N],R[N];
int d1[N],d2[N],d[N];
void BFS(int x,int *d){
queue<int> q;
if(x) fill(d+1,d+n+1,INF),d[x]=0,q.emplace(x);
else for(int i=1;i<=n;i++) q.emplace(i);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=1;i<=n;i++) if(L[i]<=x&&x<=R[i]&&d[i]>d[x]+1) d[i]=d[x]+1,q.emplace(i);
}
}
int main(){
int i,j,h;scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
BFS(1,d1);BFS(n,d2);
for(i=1;i<=n;i++) d[i]=d1[i]+d2[i];
BFS(0,d);
int q;scanf("%d",&q);while(q--){
int x;scanf("%d",&x);
printf("%d\n",d[x]>n+1?-1:d[x]);
}
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 6
Accepted
time: 1ms
memory: 5736kb
input:
2 1 1 1 2 1 1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
2 1 2 2 2 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -6
Time Limit Exceeded
input:
196001 1 408 2 37822 1 1221 1 160899 4 62751 3 21706 2 4118 8 70696 8 4916 3 24286 9 443 8 171744 11 170980 7 3541 12 16428 8 71164 1 186827 11 234 2 23141 4 17143 21 9522 10 24 19 15936 3 15884 17 426 14 3188 17 168317 4 1560 25 35 16 39439 21 122 4 17507 8 97645 11 824 25 59856 30 9265 7 151420 37...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 16
Accepted
time: 1ms
memory: 3644kb
input:
2 1 1 1 2 1 2
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
2 1 2 2 2 1 2
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5728kb
input:
6 1 1 2 2 1 3 3 5 5 6 1 6 1 4
output:
3
result:
ok single line: '3'
Test #11:
score: -16
Wrong Answer
time: 0ms
memory: 3760kb
input:
9 1 1 2 2 3 3 1 4 2 8 5 7 4 9 8 8 9 9 1 6
output:
4
result:
wrong answer 1st lines differ - expected: '3', found: '4'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 28ms
memory: 5860kb
input:
2337 1 3 2 77 1 1397 2 222 3 62 6 1896 7 10 6 950 9 9 10 16 11 455 9 588 13 16 7 1245 9 1342 8 1727 7 122 11 653 9 1094 2 57 11 81 19 1290 6 1584 16 79 14 215 21 61 27 27 16 1458 16 198 26 180 31 31 11 240 33 36 11 121 34 1542 9 1752 14 456 36 43 36 2244 40 40 4 517 42 662 31 1350 33 162 30 843 28 1...
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 27ms
memory: 5724kb
input:
2419 1 883 1 29 3 41 4 2201 1 808 6 45 7 1456 6 134 6 1372 1 1776 4 441 7 208 5 28 4 604 7 56 9 617 8 2115 15 60 13 456 10 2071 18 23 18 39 5 39 21 35 4 75 25 44 24 640 21 30 4 860 30 31 18 78 32 779 1 927 33 34 19 59 34 181 21 502 23 155 39 39 2 254 30 641 42 50 10 2000 41 2220 18 632 35 48 27 905 ...
output:
3 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 5 5 4 5 5 4 5 4 5 5 5 4 6 5 5 4 5 5 5 5 5 -1 4 5 5 4 4 5 5 5 4 4 5 5 4 -1 4 5 5 5 4 -1 5 5 5 4 5 5 5 5 5 5 4 4 5 6 5 4 4 5 5 4 5 5 4 5 4 5 5 -1 -1 4 5 5 4 5 5 4 5 4 5 6 5 5 5 5 4 5 5 5 4 5 6 5 5 5 5 5 4 5 5 5 5 5 5 5 4 5 5 5 -1 5 4 4 4 5 5 5 6 5 5 4 5 5 6 -1 5 5 5 5...
result:
wrong answer 2nd lines differ - expected: '3', found: '4'
Subtask #5:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
input:
196830 1 67357 2 183304 3 23390 4 54 1 145887 3 27807 3 12376 1 1013 3 113274 3 191874 6 23342 9 2113 13 94245 3 141449 10 1727 3 51 17 99028 6 193803 8 7452 6 121537 9 23658 18 611 6 4756 4 5141 8 8547 8 66922 13 7021 9 72 3 53043 16 167381 2 15530 5 192 33 33 9 92655 10 36182 20 19992 36 24454 1 6...