Submission #95116

#	Time	Username	Problem	Language	Result	Execution time	Memory
95116		Alexa2001	Tropical Garden (IOI11_garden)	C++17	100 / 100	271 ms	43552 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], W[Nmax];

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

void dfs_down(int node, int level, int where) /// where = unde ar fi la momentul 0
{
    if(active[node])
        W[where].push_back(level);

    for(auto it : edge[node])
        dfs_down(it, level+1, (where - 1 + CycleNr) % CycleNr );
}

void precalc(int node)
{
    memset(used, 0, sizeof(used));
    memset(on_cycle, 0, sizeof(on_cycle));
    memset(pos_cycle, 0, sizeof(pos_cycle));

    int i;
    for(i=0; i<2*m; ++i)
    {
        edge[i].clear();
        W[i].clear();
    }

    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];
    }

    for(i=0; i<2*m; ++i)
        if(!on_cycle[i]) edge[go[i]].push_back(i);

    for(i=0; i<2*m; ++i)
        if(on_cycle[i]) dfs_down(i, 0, pos_cycle[i]);

    for(i=0; i<CycleNr; ++i) sort(W[i].begin(), W[i].end());
}

int cate(vector<int> &v, int x)
{
    int st = 0, dr = v.size() - 1, mid;
    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(v[mid] <= x) st = mid+1;
            else dr = mid-1;
    }
    return st;
}

void dfs_down2(int node, vector<int> &v, int level = 0)
{
    if(active[node]) v[level] ++;
    for(auto it : edge[node])
        dfs_down2(it, v, level + 1);
}

void solve(int Q, int q[], int ans[], int Node)
{
    precalc(Node);

    int step;
    if(on_cycle[Node])
    {
        for(step = 0; step < Q; ++step)
        {
            int group = (pos_cycle[Node] - q[step] % CycleNr + CycleNr) % CycleNr;
            assert(group >= 0 && group < CycleNr);
            ans[step] += cate(W[group], q[step]); /// cate in group sunt <= q[i]
        }
        return;
    }

    ///

    vector<int> levels;
    levels.resize(Nmax);
    dfs_down2(Node, levels);

    for(step = 0; step < Q; ++step)
        if(q[step] < Nmax - 2) ans[step] += levels[q[step]];
}

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);

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

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

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31