oj.uz

Submission #162476

# Submission time Handle Problem Language Result Execution time Memory
162476 2019-11-08T10:33:24 Z MvC Toll (BOI17_toll) C++11
10 / 100
 72 ms 4344 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=5e4+50;
const int mod=1e9+7;
using namespace std;
int k,n,m,x,y,t,f[nmax],z,i,j,q,g[nmax];
vector<pair<int,int> >a[nmax];
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>k>>n>>m>>q;
	while(m--)
	{
		cin>>x>>y>>t;
		a[x].pb(mkp(y,t));
	}
	for(i=0;i<n;i++)g[i]=inf;
	g[0]=0;
	for(i=0;i<n;i++)
	{
		if(g[i]==inf)continue;
		for(j=0;j<(int)a[i].size();j++)
		{
			z=a[i][j].fr,t=a[i][j].sc;
			g[z]=min(g[z],g[i]+t);
		}
	}
	while(q--)
	{
		cin>>x>>y;
		if(y/k<=x/k)cout<<-1<<'\n';
		else if(!x)
		{
			if(g[y]==inf)cout<<-1<<'\n';
			else cout<<g[y]<<'\n';
		}
		else if(k==1)
		{
			if(g[y]==inf)cout<<-1<<'\n';
			else cout<<g[y]-(x?g[x-1]:0)<<'\n';
		}
		else
		{
			for(i=x;i<=y;i++)f[i]=inf;
			f[x]=0;
			for(i=x;i<=y;i++)
			{
				if(f[i]==inf)continue;
				for(j=0;j<(int)a[i].size();j++)
				{
					z=a[i][j].fr,t=a[i][j].sc;
					f[z]=min(f[z],f[i]+t);
				}
			}
			if(f[y]==inf)cout<<-1<<'\n';
			else cout<<f[y]<<'\n';
		}
	}
	return 0;
}

Compilation message

toll.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
toll.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3332 KB Output is correct
2 Correct 3 ms 1500 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1548 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct
8 Correct 6 ms 1628 KB Output is correct
9 Correct 29 ms 3320 KB Output is correct
10 Correct 70 ms 4248 KB Output is correct
11 Correct 52 ms 3452 KB Output is correct
12 Correct 42 ms 3180 KB Output is correct
13 Correct 72 ms 4344 KB Output is correct
14 Correct 44 ms 3348 KB Output is correct
15 Correct 36 ms 2936 KB Output is correct
16 Correct 37 ms 2936 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -