oj.uz

Submission #237393

# Submission time Handle Problem Language Result Execution time Memory
237393 2020-06-06T12:20:18 Z nicolaalexandra Tropical Garden (IOI11_garden) C++14
0 / 100
 8 ms 5248 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIM 200010
using namespace std;

int dp[DIM*2][33];
vector <pair<int,int> > L[DIM];

/*void answer (int n){
    cout<<n<<"\n";
}*/

void count_routes (int n, int m, int dest, int r[][2], int q, int g[]){

    int i,j;
    for (i=0;i<m;i++){
        int x = r[i][0] + 1, y = r[i][1] + 1;
        L[x].push_back(make_pair(i,y));
        L[y].push_back(make_pair(i,x));
    }

    for (i=1;i<=n;i++)
        sort (L[i].begin(),L[i].end());

    for (i=1;i<=n;i++){

        j = L[i][0].second;
        if (L[j][0].second != i)
            dp[i][0] = j;
        else dp[i][0] = j + n;


        if (L[i].size() >= 2){
            j = L[i][1].second;
            if (L[j][0].second != i)
                dp[i+n][0] = j;
            else dp[i+n][0] = j+n;
        } else {
            j = L[i][0].second;
            if (L[j][0].second != i)
                dp[i+n][0] = j;
            else dp[i+n][0] = j+n;
        }

    }

    for (i=1;i<=2*n;i++)
        for (j=1;j<=30;j++)
            dp[i][j] = dp[dp[i][j-1]][j-1];

    for (i=0;i<q;i++){
        int k = g[i], sol = 0;
        for (j=1;j<=n;j++){
            int nod = j, val = k;
            for (int pas=30;pas>=0;pas--){
                if ((1<<pas) <= val){
                    nod = dp[nod][pas];
                    val -= (1<<pas);
                }
            }
            if (nod == dest + 1 || nod == dest + n + 1)
                sol++;
        }
        answer(sol);
    }

}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -