Submission #49454

#	Time	Username	Problem	Language	Result	Execution time	Memory
49454		ho94949	Tropical Garden (IOI11_garden)	C++17	100 / 100	141 ms	32452 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <cstdio>
#include <vector>
#include <initializer_list>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 151515;
int N;
int minv1[MAXN], minv2[MAXN];

int outlist[2*MAXN];
vector<int> inlist[2*MAXN];
bool visit[2*MAXN];
int ans1[2*MAXN], ans2[2*MAXN];
void run(int P, int dist, int *ans, int &res, int oP)
{
    if(visit[P])
    {
        if(P == oP) res = dist;
        return;
    }
    visit[P] = true;
    if(P<N) ans[dist]++;
    for(auto x: inlist[P])
        run(x, dist+1, ans, res, oP);
}

void count_routes(int _N, int M, int P, int R[][2], int Q, int G[])
{
    N = _N;
    for(int i=0; i<N; ++i) minv1[i] = minv2[i] = -1;
    for(int i=0; i<M; ++i)
    {
        int u = R[i][0], v = R[i][1];
        for(int x: {u, v})
        {
            int y = u+v-x;
            if(minv1[x] == -1) minv1[x] = y;
            else if(minv2[x] == -1) minv2[x] = y;
        }
    }
    for(int i=0; i<N; ++i) if(minv2[i] == -1) minv2[i] = minv1[i];
    for(int i=0; i<2*N; ++i)
    {
        int to = (i<N)?minv1[i%N]:minv2[i%N];
        if(i%N == minv1[to]) to += N;
        outlist[i] = to;
        inlist[to].push_back(i);
    }
    
    int res1 = 0x3f3f3f3f, res2 = 0x3f3f3f3f;
    run(P, 0, ans1, res1, P);
    for(int i=0; i<2*N; ++i) visit[i] = false;
    run(P+N, 0, ans2, res2, P+N);
    
    for(int i=res1; i<=2*N-1; ++i)
        ans1[i] += ans1[i-res1];
    for(int i=res2; i<=2*N-1; ++i)
        ans2[i] += ans2[i-res2];
    
    for(int i=0; i<Q; ++i)
    {
        int ans = 0;
        if(G[i] < 2*N) ans += ans1[G[i]];
        else
        {
            int maxidx = (G[i]-(2*N-1))%res1 + (2*N-1) - res1;
            if(maxidx >= 0) ans += ans1[maxidx];
        }
        if(G[i] < 2*N) ans += ans2[G[i]];
        else
        {
            int maxidx = (G[i]-(2*N-1))%res2 + (2*N-1) - res2;
            if(maxidx >= 0) ans += ans2[maxidx];
        }
        answer(ans);
    }    
    return;
}

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