Submission #95108

#	Time	Username	Problem	Language	Result	Execution time	Memory
95108		Alexa2001	Tropical Garden (IOI11_garden)	C++17	49 / 100	5018 ms	15592 KiB

garden

#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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31