oj.uz

Submission #898718

# Submission time Handle Problem Language Result Execution time Memory
898718 2024-01-05T04:06:48 Z Sir_Ahmed_Imran Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 113036 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-=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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 4 ms 16984 KB Output is correct
9 Correct 6 ms 19292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 4 ms 16984 KB Output is correct
9 Correct 6 ms 19292 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 41 ms 33104 KB Output is correct
12 Correct 86 ms 43500 KB Output is correct
13 Correct 322 ms 75616 KB Output is correct
14 Correct 332 ms 106832 KB Output is correct
15 Correct 328 ms 109584 KB Output is correct
16 Correct 278 ms 80468 KB Output is correct
17 Correct 198 ms 74068 KB Output is correct
18 Correct 85 ms 43348 KB Output is correct
19 Correct 330 ms 106748 KB Output is correct
20 Correct 335 ms 109644 KB Output is correct
21 Correct 239 ms 80208 KB Output is correct
22 Correct 240 ms 73664 KB Output is correct
23 Correct 394 ms 113036 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 4 ms 16984 KB Output is correct
9 Correct 6 ms 19292 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 41 ms 33104 KB Output is correct
12 Correct 86 ms 43500 KB Output is correct
13 Correct 322 ms 75616 KB Output is correct
14 Correct 332 ms 106832 KB Output is correct
15 Correct 328 ms 109584 KB Output is correct
16 Correct 278 ms 80468 KB Output is correct
17 Correct 198 ms 74068 KB Output is correct
18 Correct 85 ms 43348 KB Output is correct
19 Correct 330 ms 106748 KB Output is correct
20 Correct 335 ms 109644 KB Output is correct
21 Correct 239 ms 80208 KB Output is correct
22 Correct 240 ms 73664 KB Output is correct
23 Correct 394 ms 113036 KB Output is correct
24 Correct 25 ms 16988 KB Output is correct
25 Execution timed out 5064 ms 33364 KB Time limit exceeded
26 Halted 0 ms 0 KB -