oj.uz

Submission #797145

# Submission time Handle Problem Language Result Execution time Memory
797145 2023-07-29T07:18:32 Z Khizri Tropical Garden (IOI11_garden) C++17
69 / 100
 164 ms 61416 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=4e5+5;
int n,m,fin,k,best[mxn][3],go[mxn][40];
vector<int>vt[mxn];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n=N,m=M,fin=P+1,k=G[0];
    for(int i=0;i<m;i++){
        int u=R[i][0]+1,v=R[i][1]+1;
        if(!best[u][0]){
            best[u][0]=v;
        }
        else if(!best[u][1]){
            best[u][1]=v;
        }
        if(!best[v][0]){
            best[v][0]=u;
        }
        else if(!best[v][1]){
            best[v][1]=u;
        }
    }
    for(int i=1;i<=n;i++){
        if(!best[i][1]){
            best[i][1]=best[i][0];
        }
    }
    for(int u=1;u<=n;u++){
        int x=best[u][0],y=best[u][1];
        if(best[x][0]==u){
            go[u][0]=x+n;
        }
        else{
            go[u][0]=x;
        }
        if(best[y][0]==u){
            go[u+n][0]=y+n;
        }
        else{
            go[u+n][0]=y;
        }
    }
    for(int i=1;i<32;i++){
        for(int u=1;u<=2*n;u++){
            go[u][i]=go[go[u][i-1]][i-1];
        }
    }
    int ans=0;
    for(int u=1;u<=n;u++){
        int node=u;
        for(int i=31;i>=0;i--){
            if(k&(1<<i)){
                node=go[node][i];
            }
        }
        if(node==fin||node==fin+n){
            ans++;
        }
    }
    answer(ans);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 7 ms 10068 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 10068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 7 ms 10068 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 10068 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 16 ms 17100 KB Output is correct
12 Correct 30 ms 22228 KB Output is correct
13 Correct 92 ms 38024 KB Output is correct
14 Correct 132 ms 54672 KB Output is correct
15 Correct 137 ms 56888 KB Output is correct
16 Correct 97 ms 41932 KB Output is correct
17 Correct 94 ms 37168 KB Output is correct
18 Correct 28 ms 22860 KB Output is correct
19 Correct 133 ms 56244 KB Output is correct
20 Correct 135 ms 56944 KB Output is correct
21 Correct 92 ms 41964 KB Output is correct
22 Correct 76 ms 37068 KB Output is correct
23 Correct 164 ms 61416 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 7 ms 10068 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 10068 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 16 ms 17100 KB Output is correct
12 Correct 30 ms 22228 KB Output is correct
13 Correct 92 ms 38024 KB Output is correct
14 Correct 132 ms 54672 KB Output is correct
15 Correct 137 ms 56888 KB Output is correct
16 Correct 97 ms 41932 KB Output is correct
17 Correct 94 ms 37168 KB Output is correct
18 Correct 28 ms 22860 KB Output is correct
19 Correct 133 ms 56244 KB Output is correct
20 Correct 135 ms 56944 KB Output is correct
21 Correct 92 ms 41964 KB Output is correct
22 Correct 76 ms 37068 KB Output is correct
23 Correct 164 ms 61416 KB Output is correct
24 Incorrect 5 ms 9764 KB Output isn't correct
25 Halted 0 ms 0 KB -