제출 #1336664

#제출 시각아이디문제언어결과실행 시간메모리
1336664trungcanKrugomet (COCI25_krugomet)C++17
70 / 70
67 ms17108 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, K, nxt[N], a[N], vis[N];
int p[20][N], h[N], ans[N];
int id[N], cnt, sz[N], root[N];
bool in[N];
vector<int> pre[N];
vector<int> cycle[N];

void dfs(int u){
    vis[u] = cnt;
    for (int k = 1; k < 17; ++k)
        p[k][u] = p[k - 1][p[k - 1][u]];

    for (int v: pre[u])
        if (!in[v]){
            p[0][v] = u;
            root[v] = root[u];
            h[v] = h[u] + 1;
            dfs(v);
        }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> K;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1, x; i <= n; ++i){
        cin >> x;
        nxt[i] = x;
        pre[x].push_back(i);
    }

    for (int i = 1; i <= n; ++i)
        if (!vis[i]){
            ++cnt;
            int u = i;
            while (!vis[u]){
                vis[u] = cnt;
                u = nxt[u];
            }
            int st = u; cycle[cnt].push_back(0);
//            cout << i << " " << cnt << "\t\t\t" << vis[2] << "\n";
            do {
                in[u] = cnt;
                cycle[cnt].push_back(u);
                id[u] = ++sz[cnt];
                u = nxt[u];
            } while (u != st);

            for (int i = 1; i <= sz[cnt]; ++i)
                root[cycle[cnt][i]] = cycle[cnt][i], dfs(cycle[cnt][i]);
//            cout << i << " " << cnt << "\t\t\t" << vis[2] << "\n";
//            cout << "\t\t" << st << " " << cnt << "\t"; for (int i = 1; i <= n; ++i) cout << vis[i] << " "; cout << "\n";
        }

//    for (int i = 1; i <= n; ++i) cout << i << " " << vis[i] << " " << in[i] << "\t" << id[i] << " " << h[i] << "\n";


    for (int i = 1; i <= n; ++i)
        if (K < h[i]){
            int cur = i;
            for (int x = K; x > 0; x ^= x & -x)
                cur = p[__builtin_ctz(x)][cur];
            ans[cur] += a[i];
        } else {
            int rm = K - h[i];
//            cout << "\t" << rm << "\n";
            int pos = (id[root[i]] + rm) % sz[vis[i]] == 0 ? sz[vis[i]] : (id[root[i]] + rm) % sz[vis[i]];
            ans[cycle[vis[i]][pos]] += a[i];
        }

    int cur = 0;
    for (int i = 1; i <= n; ++i)
        cur = max(cur, ans[i]);//, cout << ans[i] << " "; cout << "\n";
    cout << cur << "\n";
    for (int i = 1; i <= n; ++i)
        if (ans[i] == cur) cout << i << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...