제출 #1259900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259900		torment	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	100 / 100	1978 ms	60172 KiB

garden

#include "garden.h"
#include <iostream>
#include <vector>
using namespace std;
const int N = 150005;
const int LOG = 30;
vector<int> g[N], path;
int up[LOG][2 * N], tocyc[2 * N], cyc[2 * N], cycsz[2 * N], toP[2][2 * N];
bool vis[2 * N];
int kth(int k, int node){
    for(int i = LOG - 1;i >= 0;--i){
        if(k >= (1 << i)){
            k -= (1 << i);
            node = up[i][node];
        }
    }
    return node;
}
void dfs(int node){
    path.push_back(node);
    vis[node] = 1;
    if(!vis[up[0][node]]){
        dfs(up[0][node]);
    }
    else{
        if(!cycsz[up[0][node]]){    
            int sz = 1, cnt = 0;
            for(int i = (int)path.size() - 1;i >= 0 && path[i] != up[0][node];--i){
                sz++;
            }
            for(int i = (int)path.size() - 1;i >= 0 && path[i] != up[0][node];--i){
                cycsz[path[i]] = sz;
                cyc[path[i]] = cnt++;
            }
            cycsz[up[0][node]] = sz;
            cyc[up[0][node]] = cnt++;
        }
    }
    if(cycsz[node])return;
    cycsz[node] = cycsz[up[0][node]];
    tocyc[node] = tocyc[up[0][node]] + 1;
}
void answer(int x);
// void answer(int x){
//     cout << x << '\n';
// }
void count_routes(int n, int m, int p, int r[][2], int q, int k[]){
    for(int i = 0;i < m;++i){
        int u = r[i][0], v = r[i][1];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0;i < n;++i){
        if(g[i].empty())continue;
        int v = g[i][0];
        if(g[v][0] == i){
            up[0][i << 1] = ((v << 1) | 1);
        }
        else{
            up[0][i << 1] = (v << 1);
        }

        if(g[i].size() >= 2)v = g[i][1];
        else v = g[i][0];

        if(g[v][0] == i){
            up[0][(i << 1) | 1] = ((v << 1) | 1);
        }
        else{
            up[0][(i << 1) | 1] = (v << 1);
        }
    }
    for(int i = 1;i < LOG;++i){
        for(int j = 0;j < 2 * n;++j){
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }
    for(int i = 0;i < 2 * n;++i){
        if(!vis[i]){
            dfs(i);
            path.clear();
        }
    }
    // for(int i = 0;i < 2 * n;++i){
    //     cout << i << " " << cyc[i] << '\n';
    // }
    for(int i = 0;i < 2 * n;++i){
        for(int j = 0;j < 2;++j){
            int P = ((p << 1) | j);
            if(tocyc[P]){
                toP[j][i] = max(0, tocyc[i] - tocyc[P]);
            }
            else{
                int X = kth(tocyc[i], i);
                toP[j][i] = tocyc[i] + (cyc[X] - cyc[P] + cycsz[P]) % cycsz[P];
            }
            if(kth(toP[j][i], i) != P)toP[j][i] = -1;
        }
    }
    for(int i = 0;i < q;++i){
        int K = k[i], cnt = 0;
        for(int j = 0;j < 2 * n;j += 2){
            for(int l = 0;l < 2;++l){
                // cout << j / 2 << ": " << toP[l][j] << endl;
                if(toP[l][j] == -1)continue;
                int P = ((p << 1) | l);
                if(tocyc[P]){
                    cnt += (K == toP[l][j]);
                }
                else{
                    cnt += (K >= toP[l][j] && K % cycsz[P] == toP[l][j] % cycsz[P]);
                }
            }
        }
        answer(cnt);
    }
}

// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     int n, m, p;
//     cin >> n >> m >> p;
//     int r[m][2];
//     for(int i = 0;i < m;++i){
//         int u, v;
//         cin >> u >> v;
//         r[i][0] = u, r[i][1] = v;
//     }
//     int q;
//     cin >> q;
//     int k[q];
//     for(int i = 0;i < q;++i){
//         cin >> k[i];
//     }
//     count_routes(n, m, p, r, q, k);
// }

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31