제출 #1203586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203586		Hamed_Ghaffari	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	49 / 100	68 ms	42052 KiB

garden

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

const int MXN = 3e5+5;

int n, f[MXN];
vector<int> g[MXN], gg[MXN];

bool vis[MXN];
int cyc;

void dfs(int r, int v, int d=0) {
    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[MXN];
    int dis[MXN];
    solver(int v) {
        fill(vis, vis+n+n, 0);
        cyc = 0;
        dfs(v, v);
        vec.resize(cc=cyc);

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

void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
    ::n = n;
    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] = g[i][0]+(g[g[i][0]][0]==i ? n : 0);
        else f[i+n] = g[i][1]+(g[g[i][1]][0]==i ? n : 0);
    }
    for(int i=0; i<n+n; i++)
        gg[f[i]].push_back(i);
    solver A(P), B(P+n);
    for(int i=0; i<Q; i++)
        answer(A.get(G[i]) + B.get(G[i]));
}

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