oj.uz

답안 #898717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898717 2024-01-05T04:00:34 Z Sir_Ahmed_Imran 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 4 ms 17020 KB 
                              ///~~~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-=j;
                s=is[q][p];
                p=pre[q][j][s];
                q=nxt[q][j][s];
            }
            if(q==x) o++;
        }
        answer(o);
    }
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 17020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 17020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 17020 KB Output isn't correct
2 Halted 0 ms 0 KB -