oj.uz

Submission #486123

# Submission time Handle Problem Language Result Execution time Memory
486123 2021-11-10T15:01:48 Z Koosha_mv Toll (BOI17_toll) C++14
15 / 100
 3000 ms 204884 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-3);
			//eror(nxt);
			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 173 ms 200380 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 5 ms 6604 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 150 ms 200216 KB Output is correct
9 Correct 143 ms 200240 KB Output is correct
10 Correct 120 ms 198660 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 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 6 ms 6604 KB Output is correct
8 Correct 9 ms 6732 KB Output is correct
9 Correct 8 ms 6692 KB Output is correct
10 Correct 134 ms 200284 KB Output is correct
11 Correct 270 ms 201156 KB Output is correct
12 Correct 411 ms 202724 KB Output is correct
13 Correct 399 ms 202992 KB Output is correct
14 Correct 383 ms 201884 KB Output is correct
15 Correct 274 ms 122320 KB Output is correct
16 Correct 239 ms 122244 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 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 6 ms 6604 KB Output is correct
8 Correct 9 ms 6732 KB Output is correct
9 Correct 8 ms 6692 KB Output is correct
10 Correct 134 ms 200284 KB Output is correct
11 Correct 270 ms 201156 KB Output is correct
12 Correct 411 ms 202724 KB Output is correct
13 Correct 399 ms 202992 KB Output is correct
14 Correct 383 ms 201884 KB Output is correct
15 Correct 274 ms 122320 KB Output is correct
16 Correct 239 ms 122244 KB Output is correct
17 Correct 2651 ms 201284 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 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 8 ms 6732 KB Output is correct
25 Correct 17 ms 6732 KB Output is correct
26 Correct 14 ms 6776 KB Output is correct
27 Correct 137 ms 201072 KB Output is correct
28 Execution timed out 3073 ms 204884 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 200380 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 5 ms 6604 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 150 ms 200216 KB Output is correct
9 Correct 143 ms 200240 KB Output is correct
10 Correct 120 ms 198660 KB Output is correct
11 Execution timed out 3085 ms 201308 KB Time limit exceeded
12 Halted 0 ms 0 KB -