oj.uz

Submission #799845

# Submission time Handle Problem Language Result Execution time Memory
799845 2023-08-01T06:22:42 Z 반딧불(#10081) Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 18884 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void getPersonInfo();
void organizeTree();
void getAppleInfo();
void solve();

int main(){
    input();
    getPersonInfo();
    organizeTree();
    getAppleInfo();
    solve();
}

int n, k, q; ll L, C;
ll a[200002], b[200002];

void input(){
    scanf("%d %d %lld %lld", &n, &k, &L, &C);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(int i=1; i<=k; i++) scanf("%lld", &b[i]);
}

int nxt[200002]; ll delay[200002];
int par[200002]; bool inCycle[200002]; /// inCycle�� 0�� ��츸 par�� 0�� �ƴϴ�
ll dist[200002];
int cycleNum[200002], cycleIdx[200002];

vector<int> cycle[200002]; /// ����Ŭ�� ��� ���
vector<ll> cycleT[200002]; /// ���������� �� �������� ��ȸ�ϴ� �� �ɸ��� �ð�
ll cycleLength[200002]; /// �� ����Ŭ�� �ѷ�

int findNxt(ll t){ /// t ������ �
    int idx = upper_bound(a+1, a+n+1, t) - a - 1;
    if(idx == 0) idx = n;
    return idx;
}

ll findNxtTime(ll s, ll mod){
    return (s-mod+L-1)/L*L+mod;
}

void getPersonInfo(){
    for(int i=1; i<=n; i++){
        nxt[i] = findNxt((a[i]-C%L+L)%L);
        delay[i] = findNxtTime(C, (a[i] - a[nxt[i]] + L) % L);
    }

    vector<int> visited (n+1);
    for(int i=1; i<=n; i++){
        if(visited[i]) continue;
        vector<int> history;
        int x = i; ll timeSum = 0;
        while(true){
            if(visited[x]){ /// ��
                if(visited[x] == i){ /// ���ο� ����Ŭ�� ã�Ҵ�
                    int idx = find(history.begin(), history.end(), x) - history.begin();
                    /// [idx, end) �κ��� �׳� ����Ŭ�� ������ �ȴ�
                    for(int i=idx; i<(int)history.size(); i++){
                        cycle[x].push_back(history[i]);
                        cycleT[x].push_back(cycleLength[x]);
                        cycleNum[history[i]] = x, cycleIdx[history[i]] = i-idx, inCycle[history[i]] = true;
                        cycleLength[x] += delay[history[i]];
                    }
                    /// �޺κ��� �׳� Ʈ��
                    int pr = x;
                    for(int i=idx-1; i>=0; i--){
                        par[history[i]] = pr, dist[history[i]] = dist[pr] + delay[history[i]];
                        cycleNum[history[i]] = cycleNum[pr], cycleIdx[history[i]] = cycleNum[pr];
                        pr = history[i];
                    }
                }
                else{ /// �׳� Ʈ�� �Ϻκ��� ã�Ҵ�
                    int pr = x;
                    for(int i=(int)history.size()-1; i>=0; i--){
                        par[history[i]] = pr, dist[history[i]] = dist[pr] + delay[history[i]];
                        cycleNum[history[i]] = cycleNum[pr], cycleIdx[history[i]] = cycleNum[pr];
                        pr = history[i];
                    }
                }
                break;
            }

            visited[x] = i;
            history.push_back(x);
            timeSum += delay[x], x = nxt[x];
        }
    }



    #ifdef TEST
    printf("Person info done\n");
    for(int i=1; i<=n; i++){
        printf("%d: ", i);
        if(inCycle[i]) printf("in cycle, %d - %dth, dist %lld\n", cycleNum[i], cycleIdx[i], cycleT[cycleNum[i]][cycleIdx[i]]);
        else printf("in tree, par %d, dist %lld\n", par[i], dist[i]);
    }
    #endif // TEST
}

vector<int> child[200002];
int depth[200002], LCADB[200002][20];

void dfs(int x){
    for(auto y: child[x]){
        depth[y] = depth[x] + 1, par[y] = LCADB[y][0] = x;
        dfs(y);
    }
}

void organizeTree(){
    for(int i=1; i<=n; i++){
        if(par[i]) child[par[i]].push_back(i);
    }
    for(int i=1; i<=n; i++){
        if(inCycle[i]) dfs(i);
    }
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}

int appleTo[200002]; ll appleDelay[200002];

void getAppleInfo(){
    for(int i=1; i<=k; i++){
        appleTo[i] = findNxt(b[i]);
        appleDelay[i] = (b[i] - a[appleTo[i]] + L) % L;
    }
}


/// ���� ó���ϴ� �κ�

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int kthParent(int x, int k){
    for(int d=0; d<20; d++) if((k>>d)&1) x = LCADB[x][d];
    return x;
}

void solve(){
    scanf("%d", &q);
    while(q--){
        int x; ll t;
        scanf("%d %lld", &x, &t);
        ll ans = 0;

        /// ���� x�� ��尡 tree�� ���
        if(!inCycle[x]){
            int g = cycleNum[x];
            for(int i=1; i<=k; i++){
                int st = appleTo[i]; ll tim = appleDelay[i];
                if(inCycle[st] || cycleNum[st] != g || getLCA(st, x) != x) continue;
                tim += dist[st] - dist[x];
                ans += tim <= t;
            }
        }
        else{ /// �ݴ�� ����Ŭ�� ���
            int g = cycleNum[x], idx = cycleIdx[x];
            for(int i=1; i<=k; i++){
                /// �� ����� ���� ���� ����Ŭ ���� �ð��� ������ ������ش�
                int st = appleTo[i]; ll tim = appleDelay[i];
                if(cycleNum[st] != g) continue; /// �ٸ� ����Ŭ�� ��
                if(!inCycle[st]) tim += dist[st], st = cycleNum[st];

                int myIdx = cycleIdx[st];
                tim += (cycleT[g][idx] - cycleT[g][myIdx] + cycleLength[g]) % cycleLength[g];
                if(tim > t) continue; /// �ð��� �̹� ����

                ans += (t - tim) / cycleLength[g] + 1;
            }
        }
        printf("%lld\n", ans);
    }
}

Compilation message

harvest.cpp: In function 'void input()':
harvest.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d %lld %lld", &n, &k, &L, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:26:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:27:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for(int i=1; i<=k; i++) scanf("%lld", &b[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
harvest.cpp: In function 'void solve()':
harvest.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
harvest.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         scanf("%d %lld", &x, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 15 ms 15188 KB Output is correct
3 Correct 127 ms 15184 KB Output is correct
4 Correct 510 ms 14936 KB Output is correct
5 Correct 660 ms 15264 KB Output is correct
6 Correct 662 ms 15312 KB Output is correct
7 Correct 678 ms 15292 KB Output is correct
8 Correct 364 ms 15024 KB Output is correct
9 Correct 406 ms 15016 KB Output is correct
10 Correct 382 ms 15044 KB Output is correct
11 Correct 338 ms 15012 KB Output is correct
12 Correct 49 ms 15036 KB Output is correct
13 Correct 103 ms 15060 KB Output is correct
14 Correct 62 ms 15076 KB Output is correct
15 Correct 790 ms 15176 KB Output is correct
16 Correct 790 ms 15196 KB Output is correct
17 Correct 783 ms 15200 KB Output is correct
18 Correct 577 ms 15264 KB Output is correct
19 Correct 566 ms 15160 KB Output is correct
20 Correct 553 ms 15144 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 15 ms 15188 KB Output is correct
3 Correct 127 ms 15184 KB Output is correct
4 Correct 510 ms 14936 KB Output is correct
5 Correct 660 ms 15264 KB Output is correct
6 Correct 662 ms 15312 KB Output is correct
7 Correct 678 ms 15292 KB Output is correct
8 Correct 364 ms 15024 KB Output is correct
9 Correct 406 ms 15016 KB Output is correct
10 Correct 382 ms 15044 KB Output is correct
11 Correct 338 ms 15012 KB Output is correct
12 Correct 49 ms 15036 KB Output is correct
13 Correct 103 ms 15060 KB Output is correct
14 Correct 62 ms 15076 KB Output is correct
15 Correct 790 ms 15176 KB Output is correct
16 Correct 790 ms 15196 KB Output is correct
17 Correct 783 ms 15200 KB Output is correct
18 Correct 577 ms 15264 KB Output is correct
19 Correct 566 ms 15160 KB Output is correct
20 Correct 553 ms 15144 KB Output is correct
21 Execution timed out 5057 ms 18884 KB Time limit exceeded
22 Halted 0 ms 0 KB -