Submission #1243123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243123		nguyenkhangninh99	Tropical Garden (IOI11_garden)	C++20	100 / 100	67 ms	47688 KiB

garden

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

const int maxn = 3e5 + 5;

int n, f[maxn];
vector<int> g[maxn], adj[maxn];

bool vis[maxn];
int cyc;

void dfs(int r, int v, int d) {
    vis[v] = 1;
    if(!vis[f[v]]) dfs(r, f[v], d + 1);
    else if(f[v] == r) cyc = d + 1;
}

struct solver{
    int cc;
    vector<vector<int>> vec;
    int cnt[maxn], dis[maxn];

    solver(int v){
        fill(vis, vis + n + n, 0);
        fill(dis, dis + n + n, -1);
        memset(cnt, 0, sizeof(cnt));
        cyc=0;

        dfs(v, v, 0);
        vec.resize(cyc);
        cc=cyc;
        if(v < n) cnt[0]++;
        if(v < n && cc) vec[0].push_back(0);

        dis[v] = 0;
        queue<int> q;
        q.push(v);
        
        while(!q.empty()) {
            v = q.front();
            q.pop();
            for(int u: adj[v]){
                if(dis[u] == -1){
                    dis[u] = dis[v] + 1;
                    q.push(u);
                    if(u < n) cnt[dis[u]]++;
                    if(u < n && cc) vec[dis[u] % cc].push_back(dis[u]);
                }
            }
        }
    }
    int get(int k){
        if(!cc) return k >= maxn ? 0 : cnt[k];
        return upper_bound(vec[k % cc].begin(), vec[k % cc].end(), k) - vec[k % cc].begin();
    }
};

void count_routes(int sz, int m, int p, int r[][2], int q, int k[]) {
    n = sz;
    for(int i = 0; i < m; i++){
        g[r[i][0]].push_back(r[i][1]);
        g[r[i][1]].push_back(r[i][0]);
    }
    for(int i = 0; i < n; i++) {
        f[i] = g[i][0] + (g[g[i][0]][0] == i ? n : 0);
        if(g[i].size() == 1) f[i + n] = f[i];
        else f[i + n] = g[i][1] + (g[g[i][1]][0] == i ? n : 0);
    }

    for(int i = 0; i < n + n; i++) adj[f[i]].push_back(i);
    solver a(p), b(p + n);
    for(int i = 0; i < q; i++) answer(a.get(k[i]) + b.get(k[i]));
}

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