oj.uz

Submission #799928

# Submission time Handle Problem Language Result Execution time Memory
799928 2023-08-01T08:30:04 Z 반딧불(#10081) Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 16404 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 = cycle[g][cycleIdx[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 8 ms 14420 KB Output is correct
2 Correct 20 ms 15064 KB Output is correct
3 Correct 131 ms 15188 KB Output is correct
4 Correct 520 ms 15060 KB Output is correct
5 Correct 654 ms 15292 KB Output is correct
6 Correct 657 ms 15280 KB Output is correct
7 Correct 680 ms 15288 KB Output is correct
8 Correct 375 ms 14976 KB Output is correct
9 Correct 338 ms 14944 KB Output is correct
10 Correct 365 ms 15016 KB Output is correct
11 Correct 347 ms 15024 KB Output is correct
12 Correct 51 ms 14932 KB Output is correct
13 Correct 102 ms 15080 KB Output is correct
14 Correct 62 ms 15052 KB Output is correct
15 Correct 798 ms 15312 KB Output is correct
16 Correct 790 ms 15192 KB Output is correct
17 Correct 796 ms 15200 KB Output is correct
18 Correct 563 ms 15140 KB Output is correct
19 Correct 562 ms 15148 KB Output is correct
20 Correct 565 ms 15148 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 16404 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 14420 KB Output is correct
2 Correct 20 ms 15064 KB Output is correct
3 Correct 131 ms 15188 KB Output is correct
4 Correct 520 ms 15060 KB Output is correct
5 Correct 654 ms 15292 KB Output is correct
6 Correct 657 ms 15280 KB Output is correct
7 Correct 680 ms 15288 KB Output is correct
8 Correct 375 ms 14976 KB Output is correct
9 Correct 338 ms 14944 KB Output is correct
10 Correct 365 ms 15016 KB Output is correct
11 Correct 347 ms 15024 KB Output is correct
12 Correct 51 ms 14932 KB Output is correct
13 Correct 102 ms 15080 KB Output is correct
14 Correct 62 ms 15052 KB Output is correct
15 Correct 798 ms 15312 KB Output is correct
16 Correct 790 ms 15192 KB Output is correct
17 Correct 796 ms 15200 KB Output is correct
18 Correct 563 ms 15140 KB Output is correct
19 Correct 562 ms 15148 KB Output is correct
20 Correct 565 ms 15148 KB Output is correct
21 Execution timed out 5072 ms 16404 KB Time limit exceeded
22 Halted 0 ms 0 KB -