oj.uz

Submission #237395

# Submission time Handle Problem Language Result Execution time Memory
237395 2020-06-06T12:29:28 Z nicolaalexandra Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 52600 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++)
     //   cout<<dp[i][0]<<"\n";

    for (j=1;j<=30;j++)
        for (i=1;i<=2*n;i++)
            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
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5376 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 10 ms 5632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5376 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 10 ms 5632 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 24 ms 12032 KB Output is correct
12 Correct 51 ms 17688 KB Output is correct
13 Correct 123 ms 31480 KB Output is correct
14 Correct 184 ms 47992 KB Output is correct
15 Correct 182 ms 48632 KB Output is correct
16 Correct 149 ms 35960 KB Output is correct
17 Correct 135 ms 31960 KB Output is correct
18 Correct 57 ms 17528 KB Output is correct
19 Correct 191 ms 48028 KB Output is correct
20 Correct 185 ms 48632 KB Output is correct
21 Correct 153 ms 35832 KB Output is correct
22 Correct 126 ms 31736 KB Output is correct
23 Correct 218 ms 52600 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5376 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 10 ms 5632 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 24 ms 12032 KB Output is correct
12 Correct 51 ms 17688 KB Output is correct
13 Correct 123 ms 31480 KB Output is correct
14 Correct 184 ms 47992 KB Output is correct
15 Correct 182 ms 48632 KB Output is correct
16 Correct 149 ms 35960 KB Output is correct
17 Correct 135 ms 31960 KB Output is correct
18 Correct 57 ms 17528 KB Output is correct
19 Correct 191 ms 48028 KB Output is correct
20 Correct 185 ms 48632 KB Output is correct
21 Correct 153 ms 35832 KB Output is correct
22 Correct 126 ms 31736 KB Output is correct
23 Correct 218 ms 52600 KB Output is correct
24 Correct 17 ms 5120 KB Output is correct
25 Correct 3933 ms 12152 KB Output is correct
26 Execution timed out 5100 ms 17536 KB Time limit exceeded
27 Halted 0 ms 0 KB -