oj.uz

Submission #431745

# Submission time Handle Problem Language Result Execution time Memory
431745 2021-06-17T15:00:03 Z lyc Harvest (JOI20_harvest) C++14
0 / 100
 5000 ms 11912 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<ll,ll> pll;

const int mxN = 2e5+5;
const int mxM = 2e5+5;
const int lgN = 18;

int N, M, L, C, Q, A[mxN], B[mxM], e = 0;
int prv[mxN][lgN], f[mxN];
ll dst[mxN][lgN], fw[mxN];

bool used[mxN];
ll cyc[mxN];
vector<ll> harv[mxN];
vector<pll> stk;

struct Edge { int v; ll w; int id; };
vector<Edge> al[mxN];

bool found;

void dfs(int u, int p) {
    used[u] = 1;
    for (auto& [v,w,i] : al[u]) if (i != p) {
        stk.push_back(pll(u,w));
        if (!used[v]) {
            dfs(v,u);
        } else if (!found) {
            found = 1;
            ll len = 0;
            RFOR(i,SZ(stk)-1,0){
                len += stk[i].second;
                if (stk[i].first == v) break;
            }
            RFOR(i,SZ(stk)-1,0){
                cyc[stk[i].first] = len;
                if (stk[i].first == v) break;
            }
        }
        stk.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> L >> C;
    FOR(i,1,N){ cin >> A[i]; }
    FOR(i,1,M){ cin >> B[i]; }

    prv[1][0] = N, dst[1][0] = L-A[N]+A[1];
    FOR(i,2,N) prv[i][0] = i-1, dst[i][0] = A[i]-A[i-1];
    FOR(k,1,lgN-1){
        FOR(i,1,N){
            prv[i][k] = prv[prv[i][k-1]][k-1];
            dst[i][k] = dst[i][k-1] + dst[prv[i][k-1]][k-1];
        }
    }
    FOR(i,1,N){
        ll t = 0;
        int u = i;
        RFOR(k,lgN-1,0) if (t + dst[u][k] < C) {
            t += dst[u][k];
            u = prv[u][k];
        }
        f[i] = prv[u][0];
        fw[i] = t + dst[u][0];
        al[i].push_back((Edge){f[i],fw[i],e++});
        al[f[i]].push_back((Edge){i,fw[i],e++});
    }

    FOR(i,1,N) used[i] = 0, cyc[i] = 1e18+5;
    FOR(i,1,N) if (!used[i]) {
        found = 0;
        dfs(i,-1);
    }

    FOR(i,1,M){
        int fst = lower_bound(A+1,A+1+N,B[i])-A;
        ll t;
        if (fst == 1) fst = N, t = L-A[fst]+B[i];
        else --fst, t = B[i]-A[fst];

        FOR(j,1,N) used[j] = 0;
        do {
            harv[fst].push_back(t); used[fst] = 1;
            t += fw[fst];
            fst = f[fst];
        } while (!used[fst]);
    }

    //FOR(i,1,N){
    //    cout << i << ": "; for (auto& x : harv[i]){ cout << x << ' '; } cout << endl;
    //    TRACE(cyc[i]);
    //}

    cin >> Q;
    FOR(i,1,Q){
        int V; ll T; cin >> V >> T;
        ll ans = 0;
        for (auto& x : harv[V]) if (x <= T) {
            ans += (T+1-x) / cyc[V] + 1;
        }
        cout << ans << '\n';
    }
}

Compilation message

harvest.cpp: In function 'void dfs(int, int)':
harvest.cpp:33:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for (auto& [v,w,i] : al[u]) if (i != p) {
      |                ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -