# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
869131 |
2023-11-03T09:42:08 Z |
Eliorita |
Toll (BOI17_toll) |
C++14 |
|
141 ms |
99668 KB |
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int k,m,n,q,h[N],p[50010][17][6],s[50010][17][6],d[N],cur[6],nxt[6];
vector<ii> g[N],f[N];
vector<int> del;
const int inf=4557430888798830399;
void init()
{
for(int i=0;i<n;i++) h[i]=i/k+1;
for(int dep=n/k;dep>=0;dep--)
{
for(int u=dep*k;u<=dep*k+k-1;u++)
{
for(ii v : g[u])
{
p[u][0][v.x%k]=v.x;
s[u][0][v.x%k]=v.y;
}
for(int i=1;i<=16;i++)
{
for(int j=0;j<k;j++)
{
for(int l=0;l<k;l++)
{
if(p[u][i-1][l]!=inf&&p[p[u][i-1][l]][i-1][j]!=inf)
{
p[u][i][j]=p[p[u][i-1][l]][i-1][j];
s[u][i][j]=min(s[u][i][j],s[u][i-1][l]+s[p[u][i-1][l]][i-1][j]);
}
}
}
}
}
}
}
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dijkstra(int u)
{
d[u]=0;
pq.push({0,u});
while(!pq.empty())
{
int u=pq.top().y;
int du=pq.top().x;
pq.pop();
if(du!=d[u]) continue;
for(ii e : f[u])
{
int v=e.y,dv=e.x;
if(d[v]>du+dv)
{
d[v]=du+dv;
pq.push({d[v],v});
}
}
}
}
void get(int u,int v)
{
int base=h[v]-h[u],last=0;
for(int i=0;i<k;i++) cur[i]=i+(u/k)*k;
d[v]=inf;
for(int i=16;i>=0;i--)
{
if(getbit(base,i))
{
last+=(1<<i);
for(int j=0;j<k;j++)
{
// if(i==1) cout<<cur[j]<<' ';
if(cur[j]!=inf)
{
for(int l=0;l<k;l++)
{
if(s[cur[j]][i][l]!=inf)
{
del.push_back(cur[j]);
nxt[l]=1;
f[cur[j]].pb({s[cur[j]][i][l],p[cur[j]][i][l]});
// cout<<cur[j]<<' '<<p[cur[j]][i][l]<<'\n';
}
}
}
}
for(int j=0;j<k;j++)
{
// cout<<cur[j]<<' ';
if(nxt[j])
{
cur[j]=(u/k)*k+last*k+j;
d[cur[j]]=inf;
}
else cur[j]=inf;
nxt[j]=0;
}
// cout<<'\n';
}
}
dijkstra(u);
for(int u : del) f[u].clear();
del.clear();
if(d[v]==inf) cout<<-1<<'\n';
else cout<<d[v]<<'\n';
}
signed main()
{
if(fopen("demo.inp","r"))
{
freopen("demo.inp","r",stdin);
freopen("demo.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>k>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
}
memset(p,0x3f,sizeof(p));
memset(s,0x3f,sizeof(s));
init();
while(q--)
{
int u,v;
cin>>u>>v;
get(u,v);
}
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | freopen("demo.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen("demo.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
94256 KB |
Output is correct |
2 |
Correct |
12 ms |
91224 KB |
Output is correct |
3 |
Correct |
13 ms |
91224 KB |
Output is correct |
4 |
Correct |
11 ms |
91236 KB |
Output is correct |
5 |
Correct |
12 ms |
91228 KB |
Output is correct |
6 |
Correct |
14 ms |
91228 KB |
Output is correct |
7 |
Correct |
12 ms |
91224 KB |
Output is correct |
8 |
Correct |
42 ms |
93268 KB |
Output is correct |
9 |
Correct |
39 ms |
93020 KB |
Output is correct |
10 |
Correct |
25 ms |
91668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
94288 KB |
Output is correct |
2 |
Correct |
11 ms |
91228 KB |
Output is correct |
3 |
Correct |
12 ms |
91044 KB |
Output is correct |
4 |
Correct |
12 ms |
91228 KB |
Output is correct |
5 |
Correct |
13 ms |
91228 KB |
Output is correct |
6 |
Correct |
12 ms |
91224 KB |
Output is correct |
7 |
Correct |
14 ms |
91228 KB |
Output is correct |
8 |
Correct |
21 ms |
91228 KB |
Output is correct |
9 |
Correct |
42 ms |
93220 KB |
Output is correct |
10 |
Correct |
118 ms |
96592 KB |
Output is correct |
11 |
Correct |
81 ms |
94772 KB |
Output is correct |
12 |
Correct |
55 ms |
93704 KB |
Output is correct |
13 |
Correct |
88 ms |
97360 KB |
Output is correct |
14 |
Correct |
56 ms |
94680 KB |
Output is correct |
15 |
Correct |
74 ms |
94172 KB |
Output is correct |
16 |
Correct |
74 ms |
94156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
91224 KB |
Output is correct |
2 |
Correct |
12 ms |
91228 KB |
Output is correct |
3 |
Correct |
12 ms |
91040 KB |
Output is correct |
4 |
Correct |
12 ms |
91232 KB |
Output is correct |
5 |
Correct |
12 ms |
91040 KB |
Output is correct |
6 |
Correct |
12 ms |
91228 KB |
Output is correct |
7 |
Correct |
13 ms |
91228 KB |
Output is correct |
8 |
Correct |
14 ms |
91412 KB |
Output is correct |
9 |
Correct |
13 ms |
91384 KB |
Output is correct |
10 |
Correct |
37 ms |
93072 KB |
Output is correct |
11 |
Correct |
59 ms |
94168 KB |
Output is correct |
12 |
Correct |
86 ms |
95580 KB |
Output is correct |
13 |
Correct |
81 ms |
96084 KB |
Output is correct |
14 |
Correct |
70 ms |
94800 KB |
Output is correct |
15 |
Correct |
64 ms |
93780 KB |
Output is correct |
16 |
Correct |
62 ms |
93776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
91224 KB |
Output is correct |
2 |
Correct |
12 ms |
91228 KB |
Output is correct |
3 |
Correct |
12 ms |
91040 KB |
Output is correct |
4 |
Correct |
12 ms |
91232 KB |
Output is correct |
5 |
Correct |
12 ms |
91040 KB |
Output is correct |
6 |
Correct |
12 ms |
91228 KB |
Output is correct |
7 |
Correct |
13 ms |
91228 KB |
Output is correct |
8 |
Correct |
14 ms |
91412 KB |
Output is correct |
9 |
Correct |
13 ms |
91384 KB |
Output is correct |
10 |
Correct |
37 ms |
93072 KB |
Output is correct |
11 |
Correct |
59 ms |
94168 KB |
Output is correct |
12 |
Correct |
86 ms |
95580 KB |
Output is correct |
13 |
Correct |
81 ms |
96084 KB |
Output is correct |
14 |
Correct |
70 ms |
94800 KB |
Output is correct |
15 |
Correct |
64 ms |
93780 KB |
Output is correct |
16 |
Correct |
62 ms |
93776 KB |
Output is correct |
17 |
Correct |
67 ms |
95292 KB |
Output is correct |
18 |
Correct |
11 ms |
91516 KB |
Output is correct |
19 |
Correct |
12 ms |
91228 KB |
Output is correct |
20 |
Correct |
12 ms |
91228 KB |
Output is correct |
21 |
Correct |
12 ms |
91228 KB |
Output is correct |
22 |
Correct |
14 ms |
91228 KB |
Output is correct |
23 |
Correct |
14 ms |
91128 KB |
Output is correct |
24 |
Correct |
14 ms |
91368 KB |
Output is correct |
25 |
Correct |
25 ms |
91484 KB |
Output is correct |
26 |
Correct |
18 ms |
91228 KB |
Output is correct |
27 |
Correct |
50 ms |
93232 KB |
Output is correct |
28 |
Correct |
85 ms |
97872 KB |
Output is correct |
29 |
Correct |
88 ms |
98564 KB |
Output is correct |
30 |
Correct |
75 ms |
96080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
94256 KB |
Output is correct |
2 |
Correct |
12 ms |
91224 KB |
Output is correct |
3 |
Correct |
13 ms |
91224 KB |
Output is correct |
4 |
Correct |
11 ms |
91236 KB |
Output is correct |
5 |
Correct |
12 ms |
91228 KB |
Output is correct |
6 |
Correct |
14 ms |
91228 KB |
Output is correct |
7 |
Correct |
12 ms |
91224 KB |
Output is correct |
8 |
Correct |
42 ms |
93268 KB |
Output is correct |
9 |
Correct |
39 ms |
93020 KB |
Output is correct |
10 |
Correct |
25 ms |
91668 KB |
Output is correct |
11 |
Correct |
65 ms |
94288 KB |
Output is correct |
12 |
Correct |
11 ms |
91228 KB |
Output is correct |
13 |
Correct |
12 ms |
91044 KB |
Output is correct |
14 |
Correct |
12 ms |
91228 KB |
Output is correct |
15 |
Correct |
13 ms |
91228 KB |
Output is correct |
16 |
Correct |
12 ms |
91224 KB |
Output is correct |
17 |
Correct |
14 ms |
91228 KB |
Output is correct |
18 |
Correct |
21 ms |
91228 KB |
Output is correct |
19 |
Correct |
42 ms |
93220 KB |
Output is correct |
20 |
Correct |
118 ms |
96592 KB |
Output is correct |
21 |
Correct |
81 ms |
94772 KB |
Output is correct |
22 |
Correct |
55 ms |
93704 KB |
Output is correct |
23 |
Correct |
88 ms |
97360 KB |
Output is correct |
24 |
Correct |
56 ms |
94680 KB |
Output is correct |
25 |
Correct |
74 ms |
94172 KB |
Output is correct |
26 |
Correct |
74 ms |
94156 KB |
Output is correct |
27 |
Correct |
12 ms |
91224 KB |
Output is correct |
28 |
Correct |
12 ms |
91228 KB |
Output is correct |
29 |
Correct |
12 ms |
91040 KB |
Output is correct |
30 |
Correct |
12 ms |
91232 KB |
Output is correct |
31 |
Correct |
12 ms |
91040 KB |
Output is correct |
32 |
Correct |
12 ms |
91228 KB |
Output is correct |
33 |
Correct |
13 ms |
91228 KB |
Output is correct |
34 |
Correct |
14 ms |
91412 KB |
Output is correct |
35 |
Correct |
13 ms |
91384 KB |
Output is correct |
36 |
Correct |
37 ms |
93072 KB |
Output is correct |
37 |
Correct |
59 ms |
94168 KB |
Output is correct |
38 |
Correct |
86 ms |
95580 KB |
Output is correct |
39 |
Correct |
81 ms |
96084 KB |
Output is correct |
40 |
Correct |
70 ms |
94800 KB |
Output is correct |
41 |
Correct |
64 ms |
93780 KB |
Output is correct |
42 |
Correct |
62 ms |
93776 KB |
Output is correct |
43 |
Correct |
67 ms |
95292 KB |
Output is correct |
44 |
Correct |
11 ms |
91516 KB |
Output is correct |
45 |
Correct |
12 ms |
91228 KB |
Output is correct |
46 |
Correct |
12 ms |
91228 KB |
Output is correct |
47 |
Correct |
12 ms |
91228 KB |
Output is correct |
48 |
Correct |
14 ms |
91228 KB |
Output is correct |
49 |
Correct |
14 ms |
91128 KB |
Output is correct |
50 |
Correct |
14 ms |
91368 KB |
Output is correct |
51 |
Correct |
25 ms |
91484 KB |
Output is correct |
52 |
Correct |
18 ms |
91228 KB |
Output is correct |
53 |
Correct |
50 ms |
93232 KB |
Output is correct |
54 |
Correct |
85 ms |
97872 KB |
Output is correct |
55 |
Correct |
88 ms |
98564 KB |
Output is correct |
56 |
Correct |
75 ms |
96080 KB |
Output is correct |
57 |
Correct |
141 ms |
99668 KB |
Output is correct |
58 |
Correct |
44 ms |
93268 KB |
Output is correct |
59 |
Correct |
78 ms |
96156 KB |
Output is correct |