oj.uz

Submission #237420

# Submission time Handle Problem Language Result Execution time Memory
237420 2020-06-06T14:31:27 Z nicolaalexandra Tropical Garden (IOI11_garden) C++14
0 / 100
 14 ms 14592 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);

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

    int lg = dist[nxt[dest]] + 1;
    int lg2 = dist[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
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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