제출 #1259873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259873		torment	Tropical Garden (IOI11_garden)	C++20	49 / 100	26 ms	26180 KiB

garden

#include "garden.h"
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
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() == 1)continue;
        v = g[i][1];
        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 i = 0;i < 2 * n;i += 2){
            if(kth(K, i) / 2 == p)cnt++;
        }
        answer(cnt);
    }
}
// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     int n, m, p;
//     cin >> n >> m >> p;
//     vector<vector<int>>r(m, vector<int>(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;
//     vector<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: 0 / 20
• Subtask 3: 0 / 31