P14467 [COCI 2025/2026 #1] 扔球 / Krugomet 略解

Cells · 2025-11-08 18:30:11 · 题解

思路

仿照倍增 LCA 的思路，很快就能够想出来，设 st_{i, j} 表示第 i 个人的球经过 2^j 轮最终扔到的人，递推式 st_{i, j} = st_{st_{i, j - 1}, j - 1}。

然后就可以求出每个人的球经过 k 轮最终扔到的人是谁，直接把球加到这个人的答案就可以了。

时间复杂度 O(n \log{k})，可以通过。

Code

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define int LL
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 1e5 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n, k, mx;
int a[N], ans[N], st[N][40];

int find(int x, int k){
    int u = x, s = __lg(k);
    while(k){
        if(k >= (1 << s)){
            k -= (1 << s);
            u = st[u][s];
        }

        s --;
    }

    return u;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;

    rep(i, 1, n) cin >> a[i];

    rep(i, 1, n){
        int f;
        cin >> f;
        st[i][0] = f;
    }

    rep(j, 1, __lg(k))
        rep(i, 1, n)
            st[i][j] = st[st[i][j - 1]][j - 1];

    rep(i, 1, n){
        int j = find(i, k);
        ans[j] += a[i];
    }

    rep(i, 1, n) mx = max(mx, ans[i]);

    cout << mx << "\n";

    rep(i, 1, n)
        if(mx == ans[i]) cout << i << " ";

    return 0;
}

其實我根本沒人說，其實我沒你不能活，其實我給你的愛比你想的多，其實我愛你比你想的多得多……