제출 #562221

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

garden

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

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e5+10;
const ll mod=1e9+7  ;
const ll base=2e9;


/// i believe myself
/// goal 2/7
#include "garden.h"
#include "gardenlib.h"

ll mx[maxn];
ll mx1[maxn];
ll dp[maxn][2][2];
ll col[maxn][2];
pll nxt[maxn][2];
pll ed;
void dfs(ll u,ll t)
{
    col[u][t]=1;
    auto p=nxt[u][t];
    if (make_pair(u,t)==ed)
    {
        dp[u][t][t]=0;
        return ;
    }
    if (!col[p.ff][p.ss])
    {
        dfs(p.ff,p.ss);
    }
    dp[u][t][ed.ss]=min(dp[u][t][ed.ss],dp[p.ff][p.ss][ed.ss]+1);
}
ll cnt=0;
void dfs1(ll u,ll t)
{
    cnt++;
    col[u][t]=1;
    auto p=nxt[u][t];
    if (col[p.ff][p.ss])
    {
        if (p!=ed)
        {
            cnt=base;
        }
        return ;
    }
    else
    {
        dfs1(p.ff,p.ss);
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    ll n=N;
    ll m=M;
    for (int i=0; i<n; i++)
        for (int t=0; t<=1; t++)
            for (int t1=0; t1<=1; t1++)
                mx[i]=base,mx1[i]=base,dp[i][t][t1]=base;

    for (ll i=0; i<m; i++)
    {
        ll x=R[i][0];
        ll y=R[i][1];
        mx[x]=min(mx[x],i);
        mx[y]=min(mx[y],i);
    }
    for (ll i=0; i<m; i++)
    {
        ll x=R[i][0];
        ll y=R[i][1];
        if (mx[x]!=i)
            mx1[x]=min(mx1[x],i);
        if (mx[y]!=i)
            mx1[y]=min(mx1[y],i);
    }
    for (int i=0; i<n; i++)
    {
        ll nxt1=(R[mx[i]][0]+R[mx[i]][1]-i);
        nxt[i][0]=make_pair(nxt1,(mx[i]==mx[nxt1]));
        if (mx1[i]==base)
        {
            nxt[i][1]=nxt[i][0];
        }
        else
        {
            ll nxt1=(R[mx1[i]][0]+R[mx1[i]][1]-i);
            nxt[i][1]=make_pair(nxt1,(mx1[i]==mx[nxt1]));
        }
    }
    for (int t=0; t<=1; t++)
    {
        for (int i=0; i<n; i++)
            for (int t=0; t<=1; t++)
                col[i][t]=0;
        ed=make_pair(P,t);
        for (int i=0; i<n; i++)
        {
            for (int t=0; t<=1; t++)
            {
                if (!col[i][t])
                    dfs(i,t);
            }
        }
    }
    memset(col,0,sizeof(col));
    ed=make_pair(P,0);
    dfs1(P,0);
    ll cnt0=cnt;
    cnt=0;
    memset(col,0,sizeof(col));
    ed=make_pair(P,1);
    dfs1(P,1);
    ll cnt1=cnt;
    for (int i=0; i<Q; i++)
    {
        ll x=G[i];
        ll cnt=0;
        for (int i=0; i<n; i++)
        {
            bool chk=false;
            if (dp[i][0][0]!=base)
            {
                if (x>=dp[i][0][0]&&(x%cnt0)==dp[i][0][0])
                {
                    chk=true;
                }
            }
            if (dp[i][0][1]!=base)
            {
                if (x>=dp[i][0][1]&&(x%cnt1)==dp[i][0][1])
                {
                    chk=true;
                }
            }
            cnt+=chk;
        }
        answer(cnt);
    }
}

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