oj.uz

Submission #715071

# Submission time Handle Problem Language Result Execution time Memory
715071 2023-03-25T22:04:24 Z EthanKim8683 Toll (BOI17_toll) C++17
100 / 100
 437 ms 33012 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
const I N=50000;
const I T=10000;
const I K=5;
const I MAX=1e9;
vector<pair<I,I>>incs[N],outs[N];
vector<I>diss[2*N][K];
priority_queue<pair<I,I>>ques;
I k,n;
void slv(I i=1,I l=0,I r=(n-1)/k){
  if(l>r)return;
  I m=l+(r-l)/2;
  for(I j=0;j<min(k,n-m*k);j++){
    I low=l*k,mid=m*k+j,upp=min((r+1)*k,n);
    auto add=[&](I a,I dis){
      if(dis>=diss[i][j][a])return;
      if(a<0||a>=upp-low)return;
      ques.push({-(diss[i][j][a]=dis),a});
    };
    diss[i][j].resize(upp-low);
    fill(diss[i][j].begin(),diss[i][j].end(),MAX);
    diss[i][j][mid-low]=0;
    ques.push({0,mid-low});
    while(ques.size()){
      auto[dis,a]=ques.top();ques.pop();
      if((dis=-dis)!=diss[i][j][a])continue;
      for(auto[b,t]:outs[a+low])add(b-low,dis+t);
    }
    ques.push({0,mid-low});
    while(ques.size()){
      auto[dis,a]=ques.top();ques.pop();
      if((dis=-dis)!=diss[i][j][a])continue;
      for(auto[b,t]:incs[a+low])add(b-low,dis+t);
    }
  }
  slv(i<<1,l,m-1),slv(i<<1|1,m+1,r);
}
I qry(I l1,I r1,I i=1,I l2=0,I r2=(n-1)/k){
  I m=l2+(r2-l2)/2;
  if(r1/k<m)return qry(l1,r1,i<<1,l2,m-1);
  if(l1/k>m)return qry(l1,r1,i<<1|1,m+1,r2);
  I res=MAX;
  for(I j=0;j<min(k,n-m*k);j++){
    I low=l2*k,upp=min((r2+1)*k,n);
    res=min(res,diss[i][j][l1-low]+diss[i][j][r1-low]);
  }
  return res==MAX?-1:res;
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I m,o;cin>>k>>n>>m>>o;
  for(I i=0;i<m;i++){
    I a,b,t;cin>>a>>b>>t;
    outs[a].push_back({b,t});
    incs[b].push_back({a,t});
  }
  slv();
  while(o--){
    I a,b;cin>>a>>b;
    printf("%i\n",qry(a,b));
  }
}

Compilation message

toll.cpp: In function 'I qry(I, I, I, I, I)':
toll.cpp:46:16: warning: unused variable 'upp' [-Wunused-variable]
   46 |     I low=l2*k,upp=min((r2+1)*k,n);
      |                ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 21484 KB Output is correct
2 Correct 11 ms 14292 KB Output is correct
3 Correct 8 ms 14408 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 10 ms 14552 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 68 ms 22392 KB Output is correct
9 Correct 51 ms 22144 KB Output is correct
10 Correct 19 ms 18524 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 23808 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 12 ms 14628 KB Output is correct
8 Correct 14 ms 14676 KB Output is correct
9 Correct 57 ms 22308 KB Output is correct
10 Correct 270 ms 29664 KB Output is correct
11 Correct 160 ms 25552 KB Output is correct
12 Correct 86 ms 27092 KB Output is correct
13 Correct 348 ms 28860 KB Output is correct
14 Correct 169 ms 23648 KB Output is correct
15 Correct 186 ms 25172 KB Output is correct
16 Correct 178 ms 25128 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 10 ms 14396 KB Output is correct
4 Correct 8 ms 14288 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 13 ms 14676 KB Output is correct
9 Correct 12 ms 14676 KB Output is correct
10 Correct 60 ms 22240 KB Output is correct
11 Correct 152 ms 25200 KB Output is correct
12 Correct 248 ms 29564 KB Output is correct
13 Correct 257 ms 30316 KB Output is correct
14 Correct 229 ms 28384 KB Output is correct
15 Correct 175 ms 25076 KB Output is correct
16 Correct 184 ms 25032 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 10 ms 14396 KB Output is correct
4 Correct 8 ms 14288 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 13 ms 14676 KB Output is correct
9 Correct 12 ms 14676 KB Output is correct
10 Correct 60 ms 22240 KB Output is correct
11 Correct 152 ms 25200 KB Output is correct
12 Correct 248 ms 29564 KB Output is correct
13 Correct 257 ms 30316 KB Output is correct
14 Correct 229 ms 28384 KB Output is correct
15 Correct 175 ms 25076 KB Output is correct
16 Correct 184 ms 25032 KB Output is correct
17 Correct 135 ms 25168 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14412 KB Output is correct
20 Correct 9 ms 14292 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 7 ms 14292 KB Output is correct
23 Correct 9 ms 14548 KB Output is correct
24 Correct 10 ms 14548 KB Output is correct
25 Correct 16 ms 14664 KB Output is correct
26 Correct 12 ms 14676 KB Output is correct
27 Correct 65 ms 22260 KB Output is correct
28 Correct 280 ms 29564 KB Output is correct
29 Correct 272 ms 30380 KB Output is correct
30 Correct 237 ms 28476 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 21484 KB Output is correct
2 Correct 11 ms 14292 KB Output is correct
3 Correct 8 ms 14408 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 10 ms 14552 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 68 ms 22392 KB Output is correct
9 Correct 51 ms 22144 KB Output is correct
10 Correct 19 ms 18524 KB Output is correct
11 Correct 145 ms 23808 KB Output is correct
12 Correct 8 ms 14412 KB Output is correct
13 Correct 8 ms 14292 KB Output is correct
14 Correct 8 ms 14412 KB Output is correct
15 Correct 8 ms 14292 KB Output is correct
16 Correct 9 ms 14292 KB Output is correct
17 Correct 12 ms 14628 KB Output is correct
18 Correct 14 ms 14676 KB Output is correct
19 Correct 57 ms 22308 KB Output is correct
20 Correct 270 ms 29664 KB Output is correct
21 Correct 160 ms 25552 KB Output is correct
22 Correct 86 ms 27092 KB Output is correct
23 Correct 348 ms 28860 KB Output is correct
24 Correct 169 ms 23648 KB Output is correct
25 Correct 186 ms 25172 KB Output is correct
26 Correct 178 ms 25128 KB Output is correct
27 Correct 8 ms 14292 KB Output is correct
28 Correct 8 ms 14420 KB Output is correct
29 Correct 10 ms 14396 KB Output is correct
30 Correct 8 ms 14288 KB Output is correct
31 Correct 8 ms 14412 KB Output is correct
32 Correct 10 ms 14548 KB Output is correct
33 Correct 10 ms 14548 KB Output is correct
34 Correct 13 ms 14676 KB Output is correct
35 Correct 12 ms 14676 KB Output is correct
36 Correct 60 ms 22240 KB Output is correct
37 Correct 152 ms 25200 KB Output is correct
38 Correct 248 ms 29564 KB Output is correct
39 Correct 257 ms 30316 KB Output is correct
40 Correct 229 ms 28384 KB Output is correct
41 Correct 175 ms 25076 KB Output is correct
42 Correct 184 ms 25032 KB Output is correct
43 Correct 135 ms 25168 KB Output is correct
44 Correct 8 ms 14420 KB Output is correct
45 Correct 8 ms 14412 KB Output is correct
46 Correct 9 ms 14292 KB Output is correct
47 Correct 8 ms 14420 KB Output is correct
48 Correct 7 ms 14292 KB Output is correct
49 Correct 9 ms 14548 KB Output is correct
50 Correct 10 ms 14548 KB Output is correct
51 Correct 16 ms 14664 KB Output is correct
52 Correct 12 ms 14676 KB Output is correct
53 Correct 65 ms 22260 KB Output is correct
54 Correct 280 ms 29564 KB Output is correct
55 Correct 272 ms 30380 KB Output is correct
56 Correct 237 ms 28476 KB Output is correct
57 Correct 437 ms 33012 KB Output is correct
58 Correct 78 ms 22380 KB Output is correct
59 Correct 157 ms 25500 KB Output is correct