Submission #714589

#	Time	Username	Problem	Language	Result	Execution time	Memory
714589		Melika0gh	Toll (BOI17_toll)	C++17	56 / 100	3039 ms	5884 KiB

toll

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define sync        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb          push_back
#define mp          make_pair
#define fi          first
#define se          second

const int maxn = 5e4 + 10, inf = 1e9 + 7, maxsq = 400, maxlg = 21;
//const int mood2 = 97277821, mood3 = 34098487, base = 31;
vector<pair<int, int> > adj[maxn], q[maxn];
vector<int> vec;
int dp[maxn], id[maxn], res[maxn];
int k, n, m, o;

int main()
{
	cin >> k >> n >> m >> o;
	for(int i = 0; i < m; i++)
	{
		int v, u, w;
		cin >> v >> u >> w;
		adj[v].pb(mp(u, w));
	}
	for(int i = 0; i < o; i++)
	{
		int v, u;
		cin >> v >> u;
		q[u].pb(mp(v, i));
		vec.pb(u);
	}
	
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	
	for(int i = 0; i < vec.size(); i++)
		id[vec[i]] = i;
		
	for(auto x : vec)
	{
		fill(dp, dp+n, inf);
		int xx = id[x];
		dp[x] = 0;
		for(int i = x-1; i >= 0; i--)
		{
			for(auto e : adj[i])
			{
				int u = e.fi, w = e.se;
				if(dp[u] >= inf)
					continue;
				dp[i] = min(dp[i], dp[u] + w);
			}
		}
		for(auto y : q[x])
			res[y.se] = dp[y.fi];
	}
	
	for(int i = 0; i < o; i++)
	{
		if(res[i] >= inf)
			cout << -1 << '\n';
		else
			cout << res[i] << '\n';
	}
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < vec.size(); i++)
      |                 ~~^~~~~~~~~~~~
toll.cpp:45:7: warning: unused variable 'xx' [-Wunused-variable]
   45 |   int xx = id[x];
      |       ^~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44