#include <bits/stdc++.h>
using namespace std;
#define int long long
int N,M,L,C;
int people[200005];
int apple[200005];
vector<int> startapple[200005];
vector<int> adjl[200005];
bool vis[200005];
int cyclelen[200005];
int dist[200005];
bool incycle[200005];
void dfs(int node,int time_left, int &res, bool cycle){
for (auto x : startapple[node]){
//printf("startapple %lld has %lld\n",node,x);
if (x<=time_left){
res += cycle?(time_left-x)/cyclelen[node]+1:1;
}
}
vis[node] = true;
for (auto x : adjl[node]){
// printf("edge %lld %lld exists\n",node,x);
if (!vis[x]) dfs(x,time_left-(people[x]-people[node]+L)%L,res,cycle);
}
}
int find_cycle(int node, int d){
vis[node] = true;
dist[node] = d;
for (auto x : adjl[node]){
int edgel = (people[x]-people[node]+L)%L;
// printf("edge %lld %lld %lld\n",node,x,edgel);
if (vis[x]){
if (cyclelen[x]!=0) {
cyclelen[node] = cyclelen[x];
return -1;
}
cyclelen[node] = d+edgel-dist[x];
incycle[node] = true;
return x;
}
int t = find_cycle(x,d+edgel);
if (t!=-1){
incycle[node] = true;
if (t==x){
return -1;
}
return t;
}
}
return -1;
}
void set_connected(int node, int val){
vis[node] = true;
cyclelen[node] = val;
for (auto x : adjl[node]){
if (!vis[x]){
set_connected(x,val);
}
}
}
main(){
scanf("%lld%lld%lld%lld",&N,&M,&L,&C);
for (int x = 0; x<N; x++){
scanf("%lld",&people[x]);
}
for (int x = 0; x<M; x++){
scanf("%lld",&apple[x]);
}
for (int x = 0; x<M; x++){
if (apple[x]<people[0]){
startapple[N-1].push_back(L+apple[x]-people[N-1]);
}
else{
int ind = upper_bound(people,people+N,apple[x])-people-1;
startapple[ind].push_back(apple[x]-people[ind]);
}
}
for (int x = 0; x<N; x++){
int wantpos = (people[x]-C+L)%L;
// printf("%lld %lld\n",people[x],wantpos);
if (wantpos<people[0]){
adjl[N-1].push_back(x);
}
else{
int ind = upper_bound(people,people+N,wantpos)-people-1;
// printf("ind = %lld\n",ind);
adjl[ind].push_back(x);
}
}
for (int x = 0; x<N; x++){
if (!vis[x]){
find_cycle(x,0);
}
}
for (int x = 0; x<N; x++){
vis[x] = false;
}
for (int x = 0; x<N; x++){
if (!vis[x]){
if (cyclelen[x]!=0){
set_connected(x,cyclelen[x]);
}
}
// printf("cyclelen %lld = %lld\n",x,cyclelen[x]);
}
int q;
scanf("%lld",&q);
for (int x = 0; x<q; x++){
for (int x = 0; x<N; x++) vis[x] = false;
int a,b;
scanf("%lld%lld",&a,&b);
a--;
int res = 0;
dfs(a,b,res,incycle[a]);
printf("%lld\n",res);
}
}
Compilation message
harvest.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
67 | main(){
| ^~~~
harvest.cpp: In function 'int main()':
harvest.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%lld%lld%lld%lld",&N,&M,&L,&C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%lld",&people[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
harvest.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%lld",&apple[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~
harvest.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%lld",&q);
| ~~~~~^~~~~~~~~~~
harvest.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%lld%lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
19404 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
19704 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
19404 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
