oj.uz

Submission #95108

# Submission time Handle Problem Language Result Execution time Memory
95108 2019-01-27T11:22:55 Z Alexa2001 Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 15592 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

const int Nmax = 3e5 + 5;
using namespace std;

int n, m;
int Ans[Nmax], go[Nmax];
vector<int> v[Nmax], edge[Nmax];

bool on_cycle[Nmax], used[Nmax], active[Nmax];
int pos_cycle[Nmax], CycleNr;

void precalc()
{
    int node, i;
    for(i=0; i<2*m; ++i)
        edge[go[i]].push_back(i);

    node = 0;
    while(!used[node]) used[node] = 1, node = go[node];

    /// node e pe ciclu si devine pos 0

    CycleNr = 0;
    while(!on_cycle[node])
    {
        pos_cycle[node] = CycleNr ++;
        on_cycle[node] = 1;
        node = go[node];
    }
}

/// subtask 1
void solve(int Q, int q[], int ans[], int Node)
{
    int i, node, j;
    for(i=0; i<2*m; ++i)
        if(active[i])
        {
            node = i;
            for(j=0; j<q[0]; ++j)
                node = go[node];

            if(node == Node) ++ans[0];
        }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i;
    n = N; m = M;

    for(i=0; i<m; ++i)
    {
        int x, y;
        x = R[i][0];
        y = R[i][1];

        v[x].push_back(2*i); /// x->y
        v[y].push_back(2*i+1); /// y->x
    }

    set<int> S;

    for(i=0; i<m; ++i)
    {
        int x, y;
        x = R[i][0];
        y = R[i][1];

        if(v[y].size() >= 2 && v[y][0] == 2*i+1) go[2*i] = v[y][1];
            else go[2*i] = v[y][0];

        if(v[x].size() >= 2 && v[x][0] == 2*i) go[2*i+1] = v[x][1];
            else go[2*i+1] = v[x][0];

        if(y == P) S.insert(go[2*i]);
        if(x == P) S.insert(go[2*i+1]);

        if(v[x][0] == 2*i) active[2*i] = 1;
        if(v[y][0] == 2*i+1) active[2*i+1] = 1;
    }

    assert(S.size() <= 2);

  ///  precalc();

    for(auto it : S)
        solve(Q, G, Ans, it);

    for(i=0; i<Q; ++i) answer(Ans[i]);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 18 ms 14456 KB Output is correct
6 Correct 16 ms 14584 KB Output is correct
7 Correct 15 ms 14460 KB Output is correct
8 Correct 16 ms 14456 KB Output is correct
9 Correct 18 ms 14700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 18 ms 14456 KB Output is correct
6 Correct 16 ms 14584 KB Output is correct
7 Correct 15 ms 14460 KB Output is correct
8 Correct 16 ms 14456 KB Output is correct
9 Correct 18 ms 14700 KB Output is correct
10 Correct 20 ms 14456 KB Output is correct
11 Execution timed out 5018 ms 15592 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14460 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 18 ms 14456 KB Output is correct
6 Correct 16 ms 14584 KB Output is correct
7 Correct 15 ms 14460 KB Output is correct
8 Correct 16 ms 14456 KB Output is correct
9 Correct 18 ms 14700 KB Output is correct
10 Correct 20 ms 14456 KB Output is correct
11 Execution timed out 5018 ms 15592 KB Time limit exceeded
12 Halted 0 ms 0 KB -