Submission #1332603

#TimeUsernameProblemLanguageResultExecution timeMemory
1332603neptunnsKrugomet (COCI25_krugomet)C++20
70 / 70
118 ms26528 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define maxn 100005
#define mi LLONG_MIN
#define ma LLONG_MAX
#define mod 1000000007
#define pb push_back
#define S second
#define F first
const int K = (int)(log2(1000000007)) + 1;
int up[K][maxn];
vector<int> a(maxn), s(maxn);
int n, k;
void bld()
{
    for (int i = 0; i < n; i++)
    {
        up[0][i] = s[i];
    }
    for (int j = 1; j < K; j++)
    {
        for (int i = 0; i < n; i++)
        {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }
}
int getk(int i)
{
    int start = 0;
    int x = k;
    while (start < x)
    {
        while ((1 << (start + 1)) <= x)
        {
            start++;
        }
        i = up[start][i];
        x -= (1 << start);
        start = 0;
    }
    return i;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        s[i]--;
    }

    bld();
    vector<pair<int, int>> f(n, {0, 0});
    for (int i = 0; i < n; i++)
    {
        f[i].S = i;
    }
    for (int i = 0; i < n; i++)
    {
        int v = getk(i);
        f[v].F += a[i];
    }
    sort(f.begin(), f.end(), greater<>());
    vector<int> inds;
    for (int i = 0; i < n; i++)
    {
        if (f[i].F == f[0].F)
        {
            inds.pb(f[i].S + 1);
        }
        else
        {
            break;
        }
    }
    cout << f[0].F << endl;
    sort(inds.begin(), inds.end());
    for (auto it : inds)
    {
        cout << it << " ";
    }
    cout << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...