oj.uz

Submission #237434

# Submission time Handle Problem Language Result Execution time Memory
237434 2020-06-06T15:03:59 Z nicolaalexandra Tropical Garden (IOI11_garden) C++14
100 / 100
 2939 ms 35192 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIM 300010
#define INF 2000000000
using namespace std;

int nxt[DIM],dist[DIM],dist2[DIM];
vector <pair<int,int> > L[DIM];
vector <int> edg[DIM];
deque <int> c;

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

void bfs (int start, int n, int dist[]){
    int i;
    for (i=1;i<=2*n;i++)
        dist[i] = INF;

    c.clear();
    c.push_back(start);
    dist[start] = 0;

    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : edg[nod]){
            if (dist[vecin] == INF){
                dist[vecin] = 1 + dist[nod];
                c.push_back(vecin);
            }}}}

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));
    }
    dest++;

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

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

        /// duc muchia catre cea mai buna varianta

        j = L[i][0].second;
        if (L[j][0].second != i){
            edg[j].push_back(i); /// graful o sa fie pe invers
            nxt[i] = j;
        } else {
            edg[j+n].push_back(i);
            nxt[i] = j+n;
        }
        /// a doua muchie
        if (L[i].size() >= 2){
            j = L[i][1].second;
            if (L[j][0].second != i){
                edg[j].push_back(i+n);
                nxt[i+n] = j;
            } else {
                edg[j+n].push_back(i+n);
                nxt[i+n] = j+n;
            }
        } else {
            j = L[i][0].second;
            if (L[j][0].second != i){
                edg[j].push_back(i+n);
                nxt[i+n] = j;
            } else {
                edg[j+n].push_back(i+n);
                nxt[i+n] = j+n;
            }}}

    bfs (dest,n,dist);
    bfs (dest+n,n,dist2);

    //for (i=1;i<=2*n;i++)
       // cout<<dist[i]<<"\n";

    /// am doua variante de a ajunge la destinatie => doua cicluri posibile

    int lg = dist[nxt[dest]] + 1;
    int lg2 = dist2[nxt[dest+n]] + 1;

    for (i=0;i<q;i++){
        int k = g[i], sol = 0;
        for (j=1;j<=n;j++)
            if ( ((k >= dist[j]) && (k - dist[j]) % lg == 0) || (k >= dist2[j] && (k - dist2[j]) % lg2 == 0) )
                sol++;

        answer(sol);
    }

}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 14 ms 14592 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14592 KB Output is correct
9 Correct 17 ms 14848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 14 ms 14592 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14592 KB Output is correct
9 Correct 17 ms 14848 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 25 ms 17152 KB Output is correct
12 Correct 47 ms 19320 KB Output is correct
13 Correct 60 ms 26104 KB Output is correct
14 Correct 167 ms 29432 KB Output is correct
15 Correct 203 ms 29816 KB Output is correct
16 Correct 146 ms 26324 KB Output is correct
17 Correct 128 ms 25308 KB Output is correct
18 Correct 46 ms 19328 KB Output is correct
19 Correct 152 ms 29432 KB Output is correct
20 Correct 192 ms 29816 KB Output is correct
21 Correct 139 ms 26232 KB Output is correct
22 Correct 126 ms 25208 KB Output is correct
23 Correct 164 ms 30712 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 13 ms 14464 KB Output is correct
6 Correct 14 ms 14592 KB Output is correct
7 Correct 13 ms 14464 KB Output is correct
8 Correct 13 ms 14592 KB Output is correct
9 Correct 17 ms 14848 KB Output is correct
10 Correct 13 ms 14464 KB Output is correct
11 Correct 25 ms 17152 KB Output is correct
12 Correct 47 ms 19320 KB Output is correct
13 Correct 60 ms 26104 KB Output is correct
14 Correct 167 ms 29432 KB Output is correct
15 Correct 203 ms 29816 KB Output is correct
16 Correct 146 ms 26324 KB Output is correct
17 Correct 128 ms 25308 KB Output is correct
18 Correct 46 ms 19328 KB Output is correct
19 Correct 152 ms 29432 KB Output is correct
20 Correct 192 ms 29816 KB Output is correct
21 Correct 139 ms 26232 KB Output is correct
22 Correct 126 ms 25208 KB Output is correct
23 Correct 164 ms 30712 KB Output is correct
24 Correct 14 ms 14464 KB Output is correct
25 Correct 109 ms 17152 KB Output is correct
26 Correct 145 ms 19328 KB Output is correct
27 Correct 2535 ms 26232 KB Output is correct
28 Correct 965 ms 30328 KB Output is correct
29 Correct 2939 ms 30840 KB Output is correct
30 Correct 1654 ms 26872 KB Output is correct
31 Correct 1701 ms 25976 KB Output is correct
32 Correct 159 ms 19320 KB Output is correct
33 Correct 960 ms 30076 KB Output is correct
34 Correct 2918 ms 30584 KB Output is correct
35 Correct 1794 ms 26844 KB Output is correct
36 Correct 1991 ms 25976 KB Output is correct
37 Correct 743 ms 31608 KB Output is correct
38 Correct 2256 ms 35192 KB Output is correct