Submission #1265733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265733		kl0989e	Tropical Garden (IOI11_garden)	C++20	0 / 100	3 ms	4416 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;
map<pi,int> cyc;

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]});
        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]}]) {
        pi t=nxt[{p,graph[p][0]}];
        while (t.fi!=p || t.se!=graph[p][0]) {
            cyc[t]=1;
            t=nxt[t];
        }
        cyc[t]=1;
        int l1=cyc.size();
        vi f1(l1,0);
        vector<vi> f2(l1);
        for (auto [t,tdst]:dst) {
            if (cyc[t] && t.se==graph[t.fi][1]) {
                f1[tdst%l1]++;
            }
            else if (!cyc[t] && t.se==graph[t.fi][1]) {
                f2[tdst%l1].pb(tdst);
            }
        }
        for (int i=0; i<qq; i++) {
            ans[i]+=f1[g[i]%l1];
            ans[i]+=f2[g[i]%l1].end()-lower_bound(all(f2[g[i]%l1]),g[i]);
        }
    }
    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();
    cyc.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]}]) {
            pi t=nxt[{p,graph[p][1]}];
            while (t.fi!=p || t.se!=graph[p][1]) {
                cyc[t]=1;
                t=nxt[t];
            }
            cyc[t]=1;
            int l1=cyc.size();
            vi f1(l1,0);
            vector<vi> f2(l1);
            for (auto [t,tdst]:dst) {
                if (cyc[t] && t.se==graph[t.fi][1]) {
                    f1[tdst%l1]++;
                }
                else if (!cyc[t] && t.se==graph[t.fi][1]) {
                    f2[tdst%l1].pb(tdst);
                }
            }
            for (int i=0; i<qq; i++) {
                ans[i]+=f1[g[i]%l1];
                ans[i]+=f2[g[i]%l1].end()-lower_bound(all(f2[g[i]%l1]),g[i]);
            }
        }
        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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31