제출 #584751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584751		perchuts	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	232 ms	95036 KiB

garden

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "garden.h"
#include "gardenlib.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e6+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<int>g[maxn], ciclo[maxn], g2[maxn];

int n, f[maxn], dist[maxn], vis[maxn], res[maxn];

// void answer(int x){cout<<x<<endl;}

void dfs(int u,int d){
    vis[u] = 2;
    dist[u] = d;
    for(auto v:g2[u]){
        if(vis[v]!=2)dfs(v,d+1);
    }
}

void compute(int P, int Q,int G[]){
    for(int i=0;i<=2*n;++i){
        vis[i] = dist[i] = 0;
        ciclo[i].clear();
    }
    int cur = P, tciclo = 0;
    while(vis[cur]==0){
        vis[cur] = 1, cur = f[cur];
    }
    while(vis[cur]==1){
        vis[cur] = 2, cur = f[cur], ++tciclo;
    }
    //achei o ciclo da componente de p
    if(vis[P]==1){
        tciclo = 1e9, vis[f[P]] = 2;
        dfs(P,0);
        vis[f[P]] = 0;
    }else{
        cur = P;
        int d = tciclo;
        do{
            dfs(cur, d%tciclo), cur = f[cur], d--;
        } while(cur!=P);
        if(P<n)ciclo[0].pb(tciclo);
    }
    for(int i=0;i<n;++i){
        if(vis[i]&&dist[i]){
            ciclo[dist[i]%tciclo].pb(dist[i]);                
        }
    }
    for(int i=0;i<min(tciclo,3*n);++i){
        sort(all(ciclo[i]));
    }
    for(int i=0;i<Q;++i){
        int cur = G[i];
        if(tciclo==1e9&&cur>2*n)continue;
        int ans = upper_bound(all(ciclo[cur%tciclo]),cur) - begin(ciclo[cur%tciclo]);
        res[i] += ans;
    }
    
}

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){
        int u = R[i][0], v = R[i][1];
        g[u].pb(v), g[v].pb(u);
    }
    //grafo funcional, achar distancia de cada vertice pra p   
    for(int i=0;i<2*n;++i){
        int act = i%n;
        if(i<n||sz(g[act])==1){
            int best = g[act][0];
            if(g[best][0]==act)f[i] = best+n;
            else f[i] = best;
        }else{
            if(g[g[act][1]][0]==act)f[i] = g[act][1] + n;
            else f[i] = g[act][1];
        }
        g2[i].pb(f[i]), g2[f[i]].pb(i);
        // cout<<i<<" "<<f[i]<<endl;
    }

    compute(P,Q,G), compute(P+n,Q,G);

    for(int i=0;i<Q;++i){
        answer(res[i]);
    }
}

// int v[maxn][2], queries[maxn];

// int main(){
//     int n,m,p,q;cin>>n>>m>>p>>q;
//     for(int i=0;i<m;++i){
//         cin>>v[i][0]>>v[i][1];
//     }
//     for(int i=0;i<q;++i)cin>>queries[i];
//     count_routes(n,m,p,v,q,queries);
// }

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