Submission #49789

#	Time	Username	Problem	Language	Result	Execution time	Memory
49789		gs13105	Tropical Garden (IOI11_garden)	C++17	100 / 100	69 ms	13788 KiB

garden

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

void answer(int x);

const int MAXN = 150000;
const int MAXN2 = MAXN * 2;

int arr[MAXN2 + 10];
int dis[2][MAXN2 + 10];
bool chk[2][MAXN2 + 10];

void f(int x, int p)
{
    chk[p % 2][x] = 1;
    if(arr[x] == p)
    {
        dis[p % 2][x] = 1;
        return;
    }

    if(!chk[p % 2][arr[x]])
        f(arr[x], p);

    if(dis[p % 2][arr[x]])
        dis[p % 2][x] = dis[p % 2][arr[x]] + 1;
}

int mem1[MAXN + 10];
int mem2[MAXN + 10];
int sum[2][MAXN2 + 10];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    memset(mem1, -1, sizeof mem1);
    memset(mem2, -1, sizeof mem2);
    memset(arr, -1, sizeof arr);
    for(int i = 0; i < M; i++)
    {
        int x = R[i][0];
        int y = R[i][1];

        if(mem1[x] == -1)
            mem1[x] = y;
        else if(mem2[x] == -1)
            mem2[x] = y;

        if(mem1[y] == -1)
            mem1[y] = x;
        else if(mem2[y] == -1)
            mem2[y] = x;
    }

    for(int i = 0; i < N; i++)
    {
        if(mem1[mem1[i]] == i && mem2[mem1[i]] != -1)
            arr[2 * i] = 2 * mem1[i] + 1;
        else
            arr[2 * i] = 2 * mem1[i];

        if(mem2[i] != -1)
        {
            if(mem1[mem2[i]] == i && mem2[mem2[i]] != -1)
                arr[2 * i + 1] = 2 * mem2[i] + 1;
            else
                arr[2 * i + 1] = 2 * mem2[i];
        }
    }

    for(int r = 0; r < 2; r++)
        for(int i = 0; i < 2 * N; i++)
            if(!chk[r][i] && arr[i] != -1)
                f(i, 2 * P + r);

    for(int r = 0; r < 2; r++)
        for(int i = 0; i < N; i++)
            if(dis[r][2 * i])
                sum[r][dis[r][2 * i]]++;

    for(int r = 0; r < 2; r++)
    {
        int c = dis[r][2 * P + r];
        if(!c)
            continue;

        for(int i = 1; i <= 2 * N; i++)
            if(i - c >= 1)
                sum[r][i] += sum[r][i - c];
    }

    int c[2] = { dis[0][2 * P], dis[1][2 * P + 1] };
    if(!c[0])
        c[0] = c[1];
    if(!c[1])
        c[1] = c[0];
    for(int i = 0; i < Q; i++)
    {
        int ans = 0;
        for(int r=0;r<2;r++)
        {
            int t = G[i];
            if(t > 2 * N && c[r])
                t -= ((t - 2 * N + c[r] - 1) / c[r]) * c[r];

            if(t <= 2 * N)
                ans += sum[r][t];
        }
        answer(ans);
    }
}

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