Submission #27020

#	Time	Username	Problem	Language	Result	Execution time	Memory
27020		repeating	Tropical Garden (IOI11_garden)	C++11	100 / 100	4790 ms	68704 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()
#define MAX_R  1000000
#define MAX_N 1000000
#define MAX_M 1000000

using namespace std;
const long long INF = 1e9+5e8;
const int MX=1500005;
int n,m,pos;
vector<pii> adj[MX];
pii dp[MX][2];
pii DP(int ver,int flag){
    if(ver==pos)
        R {0,flag};
    pii &ret=dp[ver][flag];
    if(ret.F!=-1)R ret;
    ret={INF,flag};
    if(flag==1&&adj[ver].SI==1)
        R ret=DP(ver,0);
    int node=adj[ver][flag].S,edge=adj[ver][flag].F;
    if(adj[node][0].F==edge)
        ret=DP(node,1);
    else ret=DP(node,0);
    ret.F++;
    R ret;
}
void build(){
    MEM(dp,-1);
    for(int i=0;i<n;i++){
        DP(i,0);
        DP(i,1);
    }
    int node=adj[pos][0].S,edge=adj[pos][0].F;
    if(adj[node][0].F==edge)
        dp[pos][0]=DP(node,1),dp[pos][0].F++;
    else dp[pos][0]=DP(node,0),dp[pos][0].F++;
    if(adj[pos].SI==1)
        dp[pos][1]=dp[pos][0];
    else{
        node=adj[pos][1].S,edge=adj[pos][1].F;
        if(adj[node][0].F==edge)
            dp[pos][1]=DP(node,1),dp[pos][1].F++;
        else dp[pos][1]=DP(node,0),dp[pos][1].F++;
    }
}
int way(int ver,int flag,int k){
    if(k<0)R 0;
    if(k==0)R 1;
    if(ver!=pos)R way(pos,dp[ver][flag].S,k-dp[ver][flag].F);
    int sum=INF;
    if(dp[pos][0].S==1&&dp[pos][1].S==0){
        sum=dp[pos][0].F+dp[pos][1].F;
    }
    if(dp[pos][flag].S==flag){
        sum=dp[pos][flag].F;
    }
    R way(pos,dp[pos][flag].S,(k-dp[pos][flag].F)%sum);
}
int solve(int dis){
    int ret=0;
    for(int i=0;i<n;i++){
        ret+=way(i,0,dis);
    }
    R ret;
}
void count_routes(int N, int M, int PP, int r[][2], int Q, int G[])
{
    n=N,m=M,pos=PP;
    for(int i=0;i<m;i++){
        adj[r[i][0]].pb({i,r[i][1]});
        adj[r[i][1]].pb({i,r[i][0]});
    }
    for(int i=0;i<n;i++){
        sort(all(adj[i]));
    }
    build();
    for(int i=0; i<Q; i++)
        answer(solve(G[i]));
}

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