Submission #1259876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259876		torment	Tropical Garden (IOI11_garden)	C++20	69 / 100	5096 ms	45128 KiB

garden

#include "garden.h"
#include <iostream>
#include <vector>
using namespace std;
const int N = 150005;
const int LOG = 30;
vector<int> g[N];
int up[LOG][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 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 < q;++i){
        int K = k[i], cnt = 0;
        for(int j = 0;j < 2 * n;j += 2){
            if(kth(K, j) / 2 == p)cnt++;
        }
        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: 0 / 31