oj.uz

답안 #162475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162475 2019-11-08T10:31:19 Z MvC Toll (BOI17_toll) C++11
10 / 100
 74 ms 6776 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]-g[x]<<'\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

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3384 KB Output is correct
2 Incorrect 3 ms 1528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 3320 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1532 KB Output is correct
7 Correct 6 ms 1656 KB Output is correct
8 Correct 7 ms 1656 KB Output is correct
9 Correct 29 ms 4216 KB Output is correct
10 Correct 68 ms 6520 KB Output is correct
11 Correct 50 ms 5112 KB Output is correct
12 Correct 41 ms 4472 KB Output is correct
13 Correct 74 ms 6776 KB Output is correct
14 Correct 46 ms 4984 KB Output is correct
15 Correct 37 ms 4216 KB Output is correct
16 Correct 38 ms 4216 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3384 KB Output is correct
2 Incorrect 3 ms 1528 KB Output isn't correct
3 Halted 0 ms 0 KB -