Submission #1131641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131641		t9unkubj	Tropical Garden (IOI11_garden)	C++20	100 / 100	2216 ms	41308 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#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;
    }
    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){
                    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;
        }
    }
};
vc<int> solve(int n,int m,int p,vc<int>u,vc<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]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }
    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);
    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&&R1.first[i]!=-1&&(k[j]>=R1.first[i]&&k[j]%R1.second==R1.first[i]%R1.second))||
            (R2.second!=-1&&R2.first[i]!=-1&&(k[j]>=R2.first[i]&&k[j]%R2.second==R2.first[i]%R2.second));
            i-=n;
        }
    }
    return ans;
}
/*
vc<int> de(int n,int m,int p,vc<int>u,vc<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]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }
    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);
    dbg(R2);
    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&&R1.first[i]!=-1&&(k[j]>=R1.first[i]&&k[j]%R1.second==R1.first[i]%R1.second))||
            (R2.second!=-1&&R2.first[i]!=-1&&(k[j]>=R2.first[i]&&k[j]%R2.second==R2.first[i]%R2.second));
            
            i-=n;
        }
    }
    
    dbg(ans);
    return ans;
}

vvc<int> brute(int n,int m,int p,vc<int>u,vc<int>v,int q,vc<int>k){
    vvc<int>ans(q);
    vvc<pair<int,int>>g(n);
    rep(i,m){
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }
    rep(j,q){
        rep(i,n){
            int pre=-1;
            int now=i;
            rep(t,k[j]){
                pair<int,int>nxt{(int)1e9,-1};
                for(auto&x:g[now]){
                    if(x.second!=pre)chmin(nxt,pair<int,int>{x.second,x.first});
                }
                
                if(nxt.second!=-1){
                    now=nxt.second;
                    pre=nxt.first;
                    continue;
                }
                now=g[now][0].first;
            }
            if(now==p)ans[j].push_back(i);
        }
    }
    return ans;
}
void check(){
    while(1){
        int ng=0;
        int n=10;
        int m=20;
        vc<int>u(m),v(m);
        rep(i,m){
            u[i]=rand()%n;
            v[i]=rand()%n;
            ng|=u[i]==v[i];
        }
        rep(i,m)REP(j,i+1,m)if(minmax(u[i],v[i])==minmax(u[j],v[j]))ng=1;
        vc<int>deg(n);
        rep(i,m){
            deg[u[i]]++;
            deg[v[i]]++;
        }
        if(*min_element(all(deg))==0)ng=1;
        int p=0;
        int q=5;
        vc<int>k(q);
        rep(i,q)k[i]=rand()%7;
        if(!ng){
            dbg("START");
            auto R1=brute(n,m,p,u,v,q,k);
            auto R2=solve(n,m,p,u,v,q,k);
            int no=0;
            rep(i,q){
                if(R1[i].size()!=R2[i]){
                    no=1;
                }
            }
            if(no){
                dbg(n,m,p,u,v,q,k);
                dbg(R1);
                dbg(R2);
                de(n,m,p,u,v,q,k);
                assert(0);
            }
        }
    }
}*/
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    vc<int>u(M),v(M);
    rep(i,M){
        u[i]={R[i][0]};
        v[i]={R[i][1]};
    }
    vc<int>p(Q);
    rep(i,Q){
        p[i]=G[i];
    }
    for(auto&x:solve(N,M,P,u,v,Q,p))answer(x);
}
/*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);
    check();
}
g++ garden/garden.cpp -D t9unkubj
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
6
*/

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