oj.uz

Submission #486121

# Submission time Handle Problem Language Result Execution time Memory
486121 2021-11-10T14:59:26 Z Koosha_mv Toll (BOI17_toll) C++14
15 / 100
 3000 ms 166468 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=400,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);
				}
			}
			if(dist[i][j]<inf){
				//cout<<i<<" "<<j<<" : "<<dist[i][j]<<endl;
			}
		}
	}
	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 127 ms 161216 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 5836 KB Output is correct
6 Correct 4 ms 5836 KB Output is correct
7 Correct 4 ms 5836 KB Output is correct
8 Correct 137 ms 161240 KB Output is correct
9 Correct 122 ms 161104 KB Output is correct
10 Correct 84 ms 159556 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 162128 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 2 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 5836 KB Output is correct
7 Correct 5 ms 5836 KB Output is correct
8 Correct 9 ms 6012 KB Output is correct
9 Correct 10 ms 5836 KB Output is correct
10 Correct 113 ms 161920 KB Output is correct
11 Correct 263 ms 163656 KB Output is correct
12 Correct 403 ms 165672 KB Output is correct
13 Correct 552 ms 166468 KB Output is correct
14 Correct 386 ms 164548 KB Output is correct
15 Correct 297 ms 100020 KB Output is correct
16 Correct 255 ms 99896 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 2 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 5836 KB Output is correct
7 Correct 5 ms 5836 KB Output is correct
8 Correct 9 ms 6012 KB Output is correct
9 Correct 10 ms 5836 KB Output is correct
10 Correct 113 ms 161920 KB Output is correct
11 Correct 263 ms 163656 KB Output is correct
12 Correct 403 ms 165672 KB Output is correct
13 Correct 552 ms 166468 KB Output is correct
14 Correct 386 ms 164548 KB Output is correct
15 Correct 297 ms 100020 KB Output is correct
16 Correct 255 ms 99896 KB Output is correct
17 Execution timed out 3093 ms 163716 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 161216 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 5836 KB Output is correct
6 Correct 4 ms 5836 KB Output is correct
7 Correct 4 ms 5836 KB Output is correct
8 Correct 137 ms 161240 KB Output is correct
9 Correct 122 ms 161104 KB Output is correct
10 Correct 84 ms 159556 KB Output is correct
11 Execution timed out 3073 ms 162128 KB Time limit exceeded
12 Halted 0 ms 0 KB -