QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104756 | #6334. Passport | ________a____ | 6 | 870ms | 113612kb | C++14 | 2.4kb | 2023-05-11 21:16:31 | 2023-05-11 21:16:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010<<2
int n,N;
#define ls p<<1
#define rs p<<1|1
vector<int> ver[MAXN],e[MAXN];
int data[MAXN];
inline void add(int u,int v,int w){
ver[u].push_back(v);
//if(!w) cout<<u<<' '<<v<<endl;
e[u].push_back(w);
}
void build(int l,int r,int p){
if(l==r){
data[p]=l;
return ;
}
data[p]=++N;
int mid=l+r>>1;
build(l,mid,ls);
build(mid+1,r,rs);
add(data[ls],data[p],0),add(data[rs],data[p],0);
}
void add(int l,int r,int x,int y,int p,int u){
//for(int i=l;i<=r;i++){
// add(i,u,1);
//}
//return ;
if(x<=l&&r<=y) {
//cout<<l<<' '<<r<<' '<<u<<endl;
return add(data[p],u,1);
}
int mid=l+r>>1;
if(mid>=x) add(l,mid,x,y,ls,u);
if(mid<y) add(mid+1,r,x,y,rs,u);
}
int dis1[MAXN],dis2[MAXN];
deque<int> q;
int vis[MAXN];
inline void dij1(){
memset(dis1,0x3f,sizeof dis1);
memset(vis,0,sizeof vis);
dis1[1]=0;
q.push_back(1);
vis[1]=1;
int u,v;
while(!q.empty()){
u=q.front(),q.pop_front();
for(int i=0;i<ver[u].size();i++) {
if(vis[v=ver[u][i]]) continue ;
dis1[v]=dis1[u]+e[u][i];
if(e[u][i]) q.push_back(v);
else q.push_front(v);
vis[v]=1;
}
}
}
inline void dij2(){
memset(dis2,0x3f,sizeof dis2);
memset(vis,0,sizeof vis);
dis2[n]=0;
q.push_back(n);
vis[n]=1;
int u,v;
while(!q.empty()){
u=q.front(),q.pop_front();
for(int i=0;i<ver[u].size();i++) {
if(vis[v=ver[u][i]]) continue ;
dis2[v]=dis2[u]+e[u][i];
if(e[u][i]) q.push_back(v);
else q.push_front(v);
vis[v]=1;
}
}
}
#define q Q
int ans[MAXN];
priority_queue<pair<int,int> > q;
inline void dij(){
memset(vis,0,sizeof vis);
for(int i=1;i<=N;i++) {
ans[i]=dis1[i]+dis2[i];
//cout<<dis1[i]<<' '<<dis2[i]<<' '<<ans[i]<<endl;
q.push(make_pair(-ans[i],i));
}
int u,v;
while(!q.empty()){
u=q.top().second,q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(int i=0;i<ver[u].size();i++) {
if(ans[v=ver[u][i]]<=ans[u]+e[u][i]) continue ;
ans[v]=ans[u]+e[u][i];
q.push(make_pair(-ans[v],v));
}
}
}
#undef q
signed main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
N=n;
build(1,n,1);
for(int i=1,l,r;i<=n;i++){
scanf("%d%d",&l,&r);
add(1,n,l,r,1,i);
}
int T;
scanf("%d",&T);
dij1(),dij2();
dij();
int x;
while(T--){
scanf("%d",&x);
if(ans[x]>n) ans[x]=-1;
printf("%d\n",ans[x]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 12ms
memory: 50572kb
input:
2 1 1 1 2 1 1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 0
Accepted
time: 7ms
memory: 50536kb
input:
2 1 2 2 2 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 788ms
memory: 109224kb
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:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 300ms
memory: 87724kb
input:
198001 1 17 1 19 1 4 2 20 3 15 6 10 1 20 3 9 3 9 10 19 6 27 8 29 12 24 3 23 8 23 16 19 11 23 1 19 13 30 19 32 4 28 15 33 23 33 8 36 16 30 23 40 11 42 27 34 20 30 21 36 31 39 30 35 32 33 29 48 27 43 33 41 25 53 28 51 29 56 37 55 35 54 36 52 35 44 31 58 36 54 42 56 47 49 41 59 37 64 44 50 34 55 41 56 ...
output:
15219
result:
ok single line: '15219'
Test #5:
score: 0
Accepted
time: 222ms
memory: 82380kb
input:
200000 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53...
output:
199999
result:
ok single line: '199999'
Test #6:
score: 0
Accepted
time: 189ms
memory: 89204kb
input:
195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195...
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 134ms
memory: 89176kb
input:
156789 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 783...
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 16
Accepted
time: 8ms
memory: 50504kb
input:
2 1 1 1 2 1 2
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 11ms
memory: 50512kb
input:
2 1 2 2 2 1 2
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 20ms
memory: 50552kb
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: 13ms
memory: 50532kb
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: 24
Accepted
time: 4ms
memory: 51180kb
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:
4
result:
ok single line: '4'
Test #20:
score: -24
Wrong Answer
time: 21ms
memory: 51092kb
input:
2486 1 12 2 8 1 7 3 12 2 11 3 15 1 8 4 11 9 15 3 21 11 13 4 15 9 21 9 19 5 15 8 20 8 25 16 24 11 29 11 23 18 23 14 32 17 24 13 27 15 30 21 34 16 29 20 35 19 32 29 34 20 39 21 43 29 40 28 43 26 44 31 45 28 43 35 38 30 40 37 46 40 43 42 42 42 45 43 54 39 51 40 51 45 54 46 57 39 53 47 53 47 54 41 59 49...
output:
315
result:
wrong answer 1st lines differ - expected: '314', found: '315'
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 8
Accepted
time: 15ms
memory: 51212kb
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 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 4 4 3 4 4 3 4 3 4 4 4 3 5 4 4 3 4 4 4 4 4 -1 3 4 4 3 3 4 4 4 3 3 4 4 3 -1 3 4 4 4 3 -1 4 4 4 3 4 4 4 4 4 4 3 3 4 5 4 3 3 4 4 3 4 4 3 4 3 4 4 -1 -1 3 4 4 3 4 4 3 4 3 4 5 4 4 4 4 3 4 4 4 3 4 5 4 4 4 4 4 3 4 4 4 4 4 4 4 3 4 4 4 -1 4 3 3 3 4 4 4 5 4 4 3 4 4 5 -1 4 4 4 4...
result:
ok 2419 lines
Test #29:
score: -8
Wrong Answer
time: 7ms
memory: 51128kb
input:
2500 1 7 1 6 1 8 1 15 5 14 2 17 5 18 8 17 2 13 3 12 3 14 12 22 4 15 6 18 14 16 8 20 6 22 10 22 12 28 11 28 20 24 12 33 16 29 23 28 20 28 19 35 18 30 24 39 20 33 19 33 30 40 23 32 26 37 28 36 30 45 35 40 36 41 34 44 34 46 29 44 37 50 33 44 39 49 35 54 40 54 39 46 36 50 47 54 44 49 46 61 42 58 41 58 4...
output:
314 314 314 314 315 315 315 315 315 315 315 315 315 315 315 314 314 314 314 314 315 314 315 315 315 314 314 315 314 314 315 315 315 315 314 315 315 315 315 314 314 315 315 314 314 315 314 315 315 314 314 314 314 314 314 314 315 314 314 314 314 314 315 315 315 315 314 315 314 314 314 314 314 314 314 ...
result:
wrong answer 4th lines differ - expected: '313', found: '314'
Subtask #5:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 870ms
memory: 113612kb
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...
output:
3 3 4 4 3 4 4 3 4 3 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 3 4 4 -1 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 3 4 4 4 4 5 4 4 4 4 4 5 4 4 4 4 4 4 4 4 4 4 4 -1 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 5 -1 4 4 4 5 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4...
result:
wrong answer 3rd lines differ - expected: '3', found: '4'