oj.uz

Submission #262681

# Submission time Handle Problem Language Result Execution time Memory
262681 2020-08-13T06:54:06 Z arnold518 Harvest (JOI20_harvest) C++14
5 / 100
 5000 ms 20072 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;

struct Query
{
	int v; ll t; int p;
};

int N, M, Q;
ll L, C, A[MAXN+10], B[MAXN+10];
Query D[MAXN+10];
ll cyc[MAXN+10];
int vis[MAXN+10];

pll to[MAXN+10];
vector<pll> adj[MAXN+10];

void dfs(int now, ll dist, vector<ll> &V)
{
	vis[now]=true;
	if(now>N) V.push_back(dist);
	for(auto nxt : adj[now])
	{
		if(vis[nxt.first]) continue;
		dfs(nxt.first, dist+nxt.second, V);
	}
}

int main()
{
	scanf("%d%d%lld%lld", &N, &M, &L, &C);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
	for(int i=1; i<=M; i++) scanf("%lld", &B[i]);
	scanf("%d", &Q);
	for(int i=1; i<=Q; i++) scanf("%d%lld", &D[i].v, &D[i].t), D[i].p=i;

	for(int i=1; i<=N; i++)
	{
		ll t=A[i]-C;
		t=(t%L+L)%L;
		int it=upper_bound(A+1, A+N+1, t)-A-1;
		if(it==0) it=N;
		ll v=((A[i]-A[it])%L+L)%L;
		ll w=(C-v+L-1)/L*L+v;
		to[i]={it, w};
		adj[it].push_back({i, w});
		//printf("%d : %d %lld\n", i, to[i].first, to[i].second);
	}

	for(int i=1; i<=M; i++)
	{
		ll t=B[i];
		int it=upper_bound(A+1, A+N+1, t)-A-1;
		if(it==0) it=N;
		ll v=((B[i]-A[it])%L+L)%L;
		to[i+N]={it, v};
		adj[it].push_back({i+N, v});
		//printf("%d : %d %lld\n", i+N, to[i+N].first, to[i+N].second);
	}

	for(int i=1; i<=N+M; i++)
	{
		if(vis[i]) continue;
		vector<int> V, V2;
		int now;
		for(now=i; vis[now]==0; now=to[now].first)
		{
			vis[now]=2;
			V.push_back(now);
		}
		if(vis[now]==1)
		{
			for(auto it : V) vis[it]=1;
			continue;
		}
		for(auto it : V) vis[it]=1;
		int t=now;
		while(!V.empty())
		{
			int p=V.back();
			V2.push_back(p);
			V.pop_back();
			if(p==t) break;
		}
		ll len=0;
		for(auto it : V2) len+=to[it].second;
		for(auto it : V2) cyc[it]=len;
	}
	//for(int i=1; i<=N+M; i++) printf("%d -> %lld\n", i, cyc[i]);

	for(int i=1; i<=Q; i++)
	{
		vector<ll> V;
		for(int j=1; j<=N+M; j++) vis[j]=0;
		dfs(D[i].v, 0, V);

		ll ans=0;
		for(auto it : V)
		{
			if(it>D[i].t) continue;
			if(cyc[D[i].v])	ans+=1+(D[i].t-it)/cyc[D[i].v];
			else ans++;
		}
		printf("%lld\n", ans);
	}
}

Compilation message

harvest.cpp: In function 'int main()':
harvest.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d%d%lld%lld", &N, &M, &L, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for(int i=1; i<=M; i++) scanf("%lld", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
harvest.cpp:41:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  for(int i=1; i<=Q; i++) scanf("%d%lld", &D[i].v, &D[i].t), D[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9984 KB Output is correct
2 Correct 29 ms 10368 KB Output is correct
3 Correct 207 ms 10368 KB Output is correct
4 Correct 50 ms 10368 KB Output is correct
5 Correct 132 ms 10496 KB Output is correct
6 Correct 133 ms 10496 KB Output is correct
7 Correct 137 ms 10744 KB Output is correct
8 Correct 29 ms 10240 KB Output is correct
9 Correct 28 ms 10240 KB Output is correct
10 Correct 28 ms 10240 KB Output is correct
11 Correct 29 ms 10240 KB Output is correct
12 Correct 249 ms 10616 KB Output is correct
13 Correct 420 ms 10616 KB Output is correct
14 Correct 183 ms 10616 KB Output is correct
15 Correct 85 ms 10368 KB Output is correct
16 Correct 87 ms 10616 KB Output is correct
17 Correct 85 ms 10488 KB Output is correct
18 Correct 81 ms 10440 KB Output is correct
19 Correct 83 ms 10368 KB Output is correct
20 Correct 84 ms 10368 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 20072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9984 KB Output is correct
2 Correct 29 ms 10368 KB Output is correct
3 Correct 207 ms 10368 KB Output is correct
4 Correct 50 ms 10368 KB Output is correct
5 Correct 132 ms 10496 KB Output is correct
6 Correct 133 ms 10496 KB Output is correct
7 Correct 137 ms 10744 KB Output is correct
8 Correct 29 ms 10240 KB Output is correct
9 Correct 28 ms 10240 KB Output is correct
10 Correct 28 ms 10240 KB Output is correct
11 Correct 29 ms 10240 KB Output is correct
12 Correct 249 ms 10616 KB Output is correct
13 Correct 420 ms 10616 KB Output is correct
14 Correct 183 ms 10616 KB Output is correct
15 Correct 85 ms 10368 KB Output is correct
16 Correct 87 ms 10616 KB Output is correct
17 Correct 85 ms 10488 KB Output is correct
18 Correct 81 ms 10440 KB Output is correct
19 Correct 83 ms 10368 KB Output is correct
20 Correct 84 ms 10368 KB Output is correct
21 Execution timed out 5048 ms 20072 KB Time limit exceeded
22 Halted 0 ms 0 KB -