Submission #119986

#	Time	Username	Problem	Language	Result	Execution time	Memory
119986		Osama_Alkhodairy	Tropical Garden (IOI11_garden)	C++17	69 / 100	5053 ms	82732 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
using namespace std;

const int maxn = 150001;
const int maxk = 31;

int n, m, p;
pair <int, int> g[maxn][maxk][2];
vector <int> v[maxn];

int go1(int node, int prev){
    if(v[node].size() == 1) return v[node][0];
    if(v[node][0] == prev) return v[node][1];
    return v[node][0];
}
int go2(int node, int idx){
    if(v[node].size() == 1) return v[node][0];
    if(idx == 1) return v[node][0];
    return v[node][1];
}
int calc(int node, int steps){
    int prev = -1;
    while(steps--){
        int pcur = node;
        node = go1(node, prev);
        prev = pcur;
    }
    return node;
}
int lift(int node, int s){
    pair <int, int> cur = make_pair(node, 1);
    for(int i = maxk - 1 ; i >= 0 ; i--){
        if((s >> i) & 1){
            cur = g[cur.first][i][cur.second];
        }
    }
    return cur.first;
}
int idx(int node, int h){
    if(v[node][0] == h) return 0;
    return 1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N;
    m = M;
    p = P;
    for(int i = 0 ; i < M ; i++){
        v[R[i][0]].push_back(R[i][1]);
        v[R[i][1]].push_back(R[i][0]);
    }
    for(int node = 0 ; node < n ; node++){
        for(int k = 0 ; k < 2 ; k++){
            int nxt = go2(node, k);
            g[node][0][k] = make_pair(nxt, idx(nxt, node));
        }
    }
    for(int j = 1 ; j < maxk ; j++){
        for(int node = 0 ; node < n ; node++){
            for(int k = 0 ; k < 2 ; k++){
                auto c = g[node][j - 1][k];
                auto nxt = g[c.first][j - 1][c.second];
                g[node][j][k] = nxt;
            }
        }
    }
    for(int i = 0 ; i < Q ; i++){
        int ans = 0;
        for(int node = 0 ; node < n ; node++){
            ans += lift(node, G[i]) == p;
        }
        answer(ans);
    }
}

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