Submission #1266071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266071		kl0989e	Tropical Garden (IOI11_garden)	C++20	100 / 100	541 ms	76740 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=1.5e5;

vector<vi> graph(maxn);

map<pi,pi> nxt;
map<pi,vector<pi>> prv;
map<pi,int> dst;

void count_routes(int n, int m, int p, int r[][2], int qq, int g[]) {
    vi ans(qq,0);
    for (int i=0; i<m; i++) {
        graph[r[i][0]].pb(r[i][1]);
        graph[r[i][1]].pb(r[i][0]);
    }
    for (int i=0; i<n; i++) {
        if (graph[i].size()==1) {
            graph[i].pb(graph[i][0]);
        }
    }
    for (int i=0; i<n; i++) {
        nxt[{i,graph[i][0]}]={graph[i][1],(i==graph[graph[i][1]][0] ? i : graph[graph[i][1]][1])};
        prv[{graph[i][1],(i==graph[graph[i][1]][0] ? i : graph[graph[i][1]][1])}].pb({i,graph[i][0]}); 
        if (graph[i][0]!=graph[i][1]) {
            nxt[{i,graph[i][1]}]={graph[i][0],(i==graph[graph[i][0]][0] ? i : graph[graph[i][0]][1])};
            prv[{graph[i][0],(i==graph[graph[i][0]][0] ? i : graph[graph[i][0]][1])}].pb({i,graph[i][1]});
        }
    }
    queue<pi> q;
    q.push({p,graph[p][0]});
    while (q.size()) {
        pi t=q.front();
        q.pop();
        for (auto to:prv[t]) {
            if (dst[to]==0) {
                dst[to]=dst[t]+1;
                q.push(to);
            }
        }
    }
    if (dst[{p,graph[p][0]}]) {
        int l1=dst[{p,graph[p][0]}];
        dst[{p,graph[p][0]}]=0;
        vector<vi> f(l1);
        for (auto [t,tdst]:dst) {
            if (t.se==graph[t.fi][1]) {
                f[tdst%l1].pb(tdst);
            }
        }
        for (int i=0; i<l1; i++) {
            sort(all(f[i]));
        }
        for (int i=0; i<qq; i++) {
            ans[i]+=lower_bound(all(f[g[i]%l1]),g[i]+1)-f[g[i]%l1].begin();
        }
    }
    else {
        map<int,int> add;
        for (auto [t,tdst]:dst) {
            if (t.se==graph[t.fi][1]) {
                add[tdst]++;
            }
        }
        for (int i=0; i<qq; i++) {
            ans[i]+=add[g[i]];
        }
    }
    dst.clear();
    if (graph[p][0]!=graph[p][1]) {
        queue<pi> q;
        q.push({p,graph[p][1]});
        while (q.size()) {
            pi t=q.front();
            q.pop();
            for (auto to:prv[t]) {
                if (dst[to]==0) {
                    dst[to]=dst[t]+1;
                    q.push(to);
                }
            }
        }
        if (dst[{p,graph[p][1]}]) {
            int l1=dst[{p,graph[p][1]}];
            dst[{p,graph[p][1]}]=0;
            vector<vi> f(l1);
            for (auto [t,tdst]:dst) {
                if (t.se==graph[t.fi][1]) {
                    f[tdst%l1].pb(tdst);
                }
            }
            for (int i=0; i<l1; i++) {
                sort(all(f[i]));
            }
            for (int i=0; i<qq; i++) {
                ans[i]+=lower_bound(all(f[g[i]%l1]),g[i]+1)-f[g[i]%l1].begin();
            }
        }
        else {
            map<int,int> add;
            for (auto [t,tdst]:dst) {
                if (t.se==graph[t.fi][1]) {
                    add[tdst]++;
                }
            }
            for (int i=0; i<qq; i++) {
                ans[i]+=add[g[i]];
            }
        }
    }
    for (int i=0; i<qq; i++) {
        answer(ans[i]);
    }
}

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