Submission #564340

#	Time	Username	Problem	Language	Result	Execution time	Memory
564340		jeqcho	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	18 ms	3284 KiB

merchant

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

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int const N=1e2+3;
int const K=1e3+3;
int b[N][K],s[N][K];
vpi adj[N];
vpi rev[N];
vector<vi>ssc;
int n,m,k;
int state[N];
stack<int>kossta;
int sscid[N];
int d[N];
int drev[N];

void kosdfs(int u)
{
	if(state[u]!=0)return;
	state[u]=1;
	trav(e,adj[u])
	{
		kosdfs(e.fi);
	}
	state[u]=2;
	kossta.push(u);
	return;
}

void kosdfs2(int u)
{
	if(state[u]!=0)return;
	ssc.back().pb(u);
	sscid[u]=sz(ssc)-1;
	state[u]=1;
	trav(e,rev[u])
	{
		kosdfs2(e.fi);
	}
	kossta.push(u);
	return;
}

void kos()
{
	fill(state,state+n,0);
	F0R(i,n)kosdfs(i);
	fill(state,state+n,0);
	while(!kossta.empty())
	{
		int u=kossta.top();
		kossta.pop();
		if(state[u]!=0)continue;
		ssc.pb({});
		kosdfs2(u);
	}
}

void dij(int src)
{
	fill(d,d+n,2e9);
	priority_queue<pii>pq;
	fill(state,state+n,0);
	pq.push({0,src});
	while(!pq.empty())
	{
		int u,w;
		tie(u,w)=pq.top();
		pq.pop();
		if(state[u]==1)continue;
		state[u]=1;
		trav(e,adj[u])
		{
			int cand = -w+e.se;
			if(cand<d[e.fi])
			{
				pq.push({-cand,e.fi});
				d[e.fi]=cand;
			}
		}
	}
}

void dijrev(int src)
{
	fill(drev,drev+n,2e9);
	priority_queue<pii>pq;
	fill(state,state+n,0);
	pq.push({0,src});
	while(!pq.empty())
	{
		int u,w;
		tie(u,w)=pq.top();
		pq.pop();
		if(state[u]==1)continue;
		state[u]=1;
		trav(e,rev[u])
		{
			int cand = -w+e.se;
			if(cand<drev[e.fi])
			{
				pq.push({-cand,e.fi});
				drev[e.fi]=cand;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m>>k;
	F0R(i,n)
	{
		F0R(j,k)
		{
			cin>>b[i][j]>>s[i][j];
		}
	}
	F0R(i,m)
	{
		int a,u,t;
		cin>>a>>u>>t;
		--a;--u;
		adj[a].pb({u,t});
		rev[u].pb({a,t});
	}
	kos();
	dij(0);
	dijrev(0);
	int mx=0;
	F0R(i,n)
	{
		F0R(j,k)
		{
			if(s[i][j]==-1||b[0][j]==-1)continue;
			mx=max(mx,(s[i][j]-b[0][j])/(d[i]+drev[i]));
		}
	}
	cout<<mx<<'\n';
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34