Submission #898718

#	Time	Username	Problem	Language	Result	Execution time	Memory
898718		Sir_Ahmed_Imran	Tropical Garden (IOI11_garden)	C++17	69 / 100	5064 ms	113036 KiB

garden

                              ///~~~LOTA~~~///
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 150000
int pwr[30];
int lv[MAXN][2];
vector<pii> a[MAXN];
int pre[MAXN][30][2];
int nxt[MAXN][30][2];
map<int,int> is[MAXN];
void count_routes(int n,int m,int x,int e[MAXN][2],int Q,int G[MAXN]){
    int o,p,q,r,s;
    for(int i=0;i<m;i++){
        a[e[i][0]].append({e[i][1],i});
        a[e[i][1]].append({e[i][0],i});
    }
    for(int i=pwr[0]=1;i<30;i++)
        pwr[i]=pwr[i-1]*2;
    for(int i=0;i<n;i++){
        p=q=m;
        for(auto& j:a[i]){
            if(j.ss<p){
                q=p;
                p=j.ss;
                lv[i][1]=lv[i][0];
                lv[i][0]=j.ff;
            }
            else if(j.ss<q){
                q=j.ss;
                lv[i][1]=j.ff;
            }
        }
        pre[i][0][0]=pre[i][0][1]=i;
        if(q==m) lv[i][1]=lv[i][0];
        nxt[i][0][0]=lv[i][0];
        nxt[i][0][1]=lv[i][1];
        is[i][lv[i][0]]=1;
    }
    for(int j=0;j<29;j++){
        for(int i=0;i<n;i++){
            nxt[i][j+1][0]=nxt[nxt[i][j][0]][j][is[nxt[i][j][0]][pre[i][j][0]]];
            pre[i][j+1][0]=pre[nxt[i][j][0]][j][is[nxt[i][j][0]][pre[i][j][0]]];
            nxt[i][j+1][1]=nxt[nxt[i][j][1]][j][is[nxt[i][j][1]][pre[i][j][1]]];
            pre[i][j+1][1]=pre[nxt[i][j][1]][j][is[nxt[i][j][1]][pre[i][j][1]]];
        }
    }
    for(int k=0;k<Q;k++){
        for(int i=o=0;i<n;i++){
            p=-1;
            q=i;
            r=G[k];
            for(int j=29;j>=0;j--){
                if(pwr[j]>r) continue;
                r-=pwr[j];
                s=is[q][p];
                p=pre[q][j][s];
                q=nxt[q][j][s];
            }
            if(q==x) o++;
        }
        answer(o);
    }
}

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