oj.uz

Submission #486124

# Submission time Handle Problem Language Result Execution time Memory
486124 2021-11-10T15:02:37 Z Koosha_mv Toll (BOI17_toll) C++14
15 / 100
 3000 ms 203060 KB 
#include <bits/stdc++.h>
using namespace std;
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define Add(x,y) x=(x+y)%mod
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=1e5+9,sq=500,K=5,inf=1e15;

int n,k,m,q,a[N],dp[N],dist[N][sq];
vector<pair<int,int> > g[N];

void tsft(int u,int v){
	f(i,v*k,v*k+k) dp[i]=inf;
	f(i,u*k,u*k+k){
		f(j,v,v*k+k){
			minm(dp[j],dp[i]+dist[i][j-i]);
		}
	}	
}

main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>k>>n>>m>>q;
	f(i,0,m){
		int u,v,t;
		cin>>u>>v>>t;
		g[u].pb(mp(v,t));
	}
	f_(i,n-1,0){
		dist[i][0]=0;
		f(j,1,sq){
			dist[i][j]=inf;
			f(p,0,g[i].size()){
				if(g[i][p].F<=i+j){
					minm(dist[i][j],dist[g[i][p].F][j-(g[i][p].F-i)]+g[i][p].S);
				}
			}
		}
	}
	f(prt,0,q){
		int a,b,u,v;
		cin>>a>>b;
		u=a/k,v=b/k;
		f(i,u*k,u*k+k) dp[i]=inf;
		dp[a]=0;
		while(u!=v){
			int nxt=min(v,u+sq/k-1);
			tsft(u,nxt);
			u=nxt;
		}
		cout<<((dp[b] == inf || b<a) ? -1 : dp[b])<<'\n';
	}
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/

Compilation message

toll.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~
toll.cpp: In function 'int main()':
toll.cpp:7:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   47 |    f(p,0,g[i].size()){
      |      ~~~~~~~~~~~~~~~           
toll.cpp:47:4: note: in expansion of macro 'f'
   47 |    f(p,0,g[i].size()){
      |    ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 200284 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 5 ms 6604 KB Output is correct
6 Correct 5 ms 6524 KB Output is correct
7 Correct 6 ms 6604 KB Output is correct
8 Correct 147 ms 200428 KB Output is correct
9 Correct 140 ms 200260 KB Output is correct
10 Correct 105 ms 198752 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 201380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 6604 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 9 ms 6692 KB Output is correct
9 Correct 7 ms 6604 KB Output is correct
10 Correct 130 ms 200260 KB Output is correct
11 Correct 344 ms 201260 KB Output is correct
12 Correct 386 ms 202664 KB Output is correct
13 Correct 466 ms 203060 KB Output is correct
14 Correct 401 ms 201860 KB Output is correct
15 Correct 274 ms 122240 KB Output is correct
16 Correct 268 ms 122232 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 6604 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 9 ms 6692 KB Output is correct
9 Correct 7 ms 6604 KB Output is correct
10 Correct 130 ms 200260 KB Output is correct
11 Correct 344 ms 201260 KB Output is correct
12 Correct 386 ms 202664 KB Output is correct
13 Correct 466 ms 203060 KB Output is correct
14 Correct 401 ms 201860 KB Output is correct
15 Correct 274 ms 122240 KB Output is correct
16 Correct 268 ms 122232 KB Output is correct
17 Correct 2595 ms 201356 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 2 ms 2636 KB Output is correct
23 Correct 5 ms 6604 KB Output is correct
24 Correct 9 ms 6604 KB Output is correct
25 Correct 18 ms 6712 KB Output is correct
26 Correct 15 ms 6696 KB Output is correct
27 Correct 136 ms 200216 KB Output is correct
28 Execution timed out 3079 ms 202732 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 200284 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 5 ms 6604 KB Output is correct
6 Correct 5 ms 6524 KB Output is correct
7 Correct 6 ms 6604 KB Output is correct
8 Correct 147 ms 200428 KB Output is correct
9 Correct 140 ms 200260 KB Output is correct
10 Correct 105 ms 198752 KB Output is correct
11 Execution timed out 3077 ms 201380 KB Time limit exceeded
12 Halted 0 ms 0 KB -