제출 #431749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431749		tqbfjotld	수확 (JOI20_harvest)	C++14	0 / 100	17 ms	19704 KiB

harvest

#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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75