oj.uz

Submission #797143

# Submission time Handle Problem Language Result Execution time Memory
797143 2023-07-29T07:17:22 Z Khizri Tropical Garden (IOI11_garden) C++17
49 / 100
 104 ms 94196 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=2e5+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 2 ms 5204 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 4 ms 5464 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 4 ms 5464 KB Output is correct
10 Correct 2 ms 5080 KB Output is correct
11 Correct 14 ms 12756 KB Output is correct
12 Correct 27 ms 18184 KB Output is correct
13 Correct 104 ms 34404 KB Output is correct
14 Runtime error 82 ms 94196 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 4 ms 5464 KB Output is correct
10 Correct 2 ms 5080 KB Output is correct
11 Correct 14 ms 12756 KB Output is correct
12 Correct 27 ms 18184 KB Output is correct
13 Correct 104 ms 34404 KB Output is correct
14 Runtime error 82 ms 94196 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -