Submission #1131510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131510		t9unkubj	Tropical Garden (IOI11_garden)	C++20	0 / 100	1 ms	576 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#ifdef t9unkubj

#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct namori{
    struct uf{
        vc<int>par;
        uf(int n=0):par(n,-1){}
        int root(int x){return (par[x]<0?x:par[x]=root(par[x]));};
        int merge(int a,int b){
            a=root(a),b=root(b);
            if(a==b)return 0;
            if(-par[a]<-par[b])swap(a,b);
            par[a]+=par[b];
            par[b]=a;
            return 1;
        }
    };
    int n;
    uf u;
    vc<int>nxt;
    vc<int>group;
    vc<int>cyc_len;
    vvc<int>orders;
    vc<int>TS_order;
    vvc<int>inv;
    vc<int>belong;
    namori(int n):n(n),nxt(n),u(n),group(n),
   inv(n),belong(n),TS_order(n){}
    void set(int a,int b){
        assert(0<=a&&a<n);
        assert(0<=b&&b<n);
        nxt[a]=b;
        dbg(a,b);
    }
    void build(){
        rep(i,n){
            inv[nxt[i]].push_back(i);
        }

        rep(i,n){
            u.merge(i,nxt[i]);
        }
        int g=0;
        rep(i,n)if(i==u.root(i))g++;
        vc<int>nm(n);
        int tmp=0;
        rep(i,n){
            if(i==u.root(i))nm[i]=tmp++;
        }
        vvc<int>gs(g);
        rep(i,n){
            gs[nm[u.root(i)]].push_back(i);
        }
        cyc_len.resize(g);
        orders.resize(g);
        vc<int>last_visit(n,-1);
        rep(i,g){
            vc<int>path;
            for(auto&x:gs[i]){
                group[x]=i;
            }        
            int T=0;
            int now=gs[i][0];
            while(1){
                if(last_visit[now]!=-1){
                    dbg(now);
                    REP(j,last_visit[now],T){
                        orders[i].push_back(path[j]);
                        TS_order[path[j]]=j-last_visit[now];
                        belong[path[j]]=1;
                    }
                    cyc_len[i]=T-last_visit[now];
                    break;
                }
                path.push_back(now);
                last_visit[now]=T++;
                now=nxt[now];
            }
        }
    }

    pair<vc<int>,int> query(int target){
        if(!belong[target]){
            pair<vc<int>,int>res{};
            res.first.resize(n,-1);
            res.second=-1;
            auto dfs=[&](auto&dfs,int u,int F)->void{
                res.first[u]=F;
                for(auto&y:inv[u]){
                    if(belong[y])continue;
                    dfs(dfs,y,F+1);
                }
            };
            dfs(dfs,target,0);
            return res;
        }else{
            pair<vc<int>,int>res{};
            
            int G=group[target];
            res.first.resize(n,-1);
            res.second=cyc_len[G];
            int a1=TS_order[target];
            auto dist=[&](int a,int b,int mod){
                if(a<=b)return b-a;
                return mod-a+b;
            };
            for(auto&x:orders[G]){
                int a2=TS_order[x];
                auto dfs=[&](auto&dfs,int u,int F)->void{
                    res.first[u]=F;
                    for(auto&y:inv[u]){
                        if(belong[y])continue;
                        dfs(dfs,y,F+1);
                    }
                };
                dfs(dfs,x,dist(a2,a1,cyc_len[G]));
            }
            return res;
        }
    }
};
void RET(int x){
    #ifdef t9unkubj
    cout<<x<<endl;
    #else
    answer(x);
    #endif
}
void solve(int n,int m,int p,vc<pair<int,int>>u,vc<pair<int,int>>v,int q,vc<int>k){
    /*
いちばん強いところから来た 0~N-1
else : N~2N-1

namoriになるので頑張る
    */
    vvc<pair<int,int>>g(n);
    rep(i,m){
        g[u[i].first].push_back({v[i].first,v[i].second});
        g[v[i].first].push_back({u[i].first,u[i].second});
    }
    rep(i,n){
        sort(all(g[i]),[](auto a,auto b){
            return a.second>b.second;
        });
    }
    vc<int>mx(n);
    rep(i,n){
        mx[i]=g[i].back().second;
    }
    namori namori(n*2);
    //最強から
    rep(i,n){
        assert(g[i].size());
        if(g[i].size()==1){
            int number=g[i][0].second;
            int go=g[i][0].first;
            if(number==mx[go]){
                namori.set(i,go);
            }else{
                namori.set(i,go+n);
            }
        }else{
            int number=g[i][g[i].size()-2].second;
            int go=g[i][g[i].size()-2].first;
            if(number==mx[go]){
                namori.set(i,go);
            }else{
                namori.set(i,go+n);
            }
        }
    }
    //最強から
    rep(i,n){
        int number=g[i].back().second;
        int go=g[i].back().first;
        if(number==mx[go]){
            namori.set(i+n,go);
        }else{
            namori.set(i+n,go+n);
        }
    }

    namori.build();

    auto R1=namori.query(p);
    auto R2=namori.query(p+n);
    dbg(R1.first,R1.second);
    dbg(R2.first,R2.second);
    vc<int>ans(q);
    rep(j,q){
        rep(i,n){
            i+=n;
            ans[j]+=
            (R1.first[i]==k[j])||
            (R2.first[i]==k[j])||
            (R1.second!=-1&&(k[j]>=R1.first[i]&&k[j]%R1.second==R1.first[i]))||
            (R2.second!=-1&&(k[j]>=R2.first[i]&&k[j]%R2.second==R2.first[i]));
            if((R1.first[i]==k[j])||
            (R2.first[i]==k[j])||
            (R1.second!=-1&&(k[j]>=R1.first[i]&&k[j]%R1.second==R1.first[i]))||
            (R2.second!=-1&&(k[j]>=R2.first[i]&&k[j]%R2.second==R2.first[i]))){
                dbg(i,j);
            }
            i-=n;
        }
        RET(ans[j]);
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    vc<pair<int,int>>u(M),v(M);
    rep(i,M){
        u[i]={R[i][0],i};
        v[i]={R[i][1],i};
    }
    vc<int>p(Q);
    rep(i,Q){
        p[i]=G[i];
    }
    solve(N,M,P,u,v,Q,p);
}
/*int main(){
    int N,M,P;
    cin>>N>>M>>P;
    int R[M][2];
    rep(i,M)rep(j,2)cin>>R[i][j];
    int Q;
    cin>>Q;
    int G[Q];
    rep(i,Q){
        cin>>G[i];
    }
    count_routes(N, M, P,  R, Q,  G);
}*/
/*
g++ garden/garden.cpp -D t9unkubj
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
*/

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