oj.uz

Submission #562227

# Submission time Handle Problem Language Result Execution time Memory
562227 2022-05-14T07:32:25 Z fcmalkcin Tropical Garden (IOI11_garden) C++17
100 / 100
 4048 ms 17848 KB 
#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);
    cnt=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]%cnt0))
                {
                    chk=true;
                }
            }
            if (dp[i][0][1]!=base)
            {
                if (x>=dp[i][0][1]&&(x%cnt1)==(dp[i][0][1]%cnt1))
                {
                    chk=true;
                }
            }
            cnt+=chk;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2004 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1972 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1852 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2004 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1972 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1852 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 7 ms 3448 KB Output is correct
12 Correct 14 ms 4544 KB Output is correct
13 Correct 31 ms 14872 KB Output is correct
14 Correct 46 ms 9952 KB Output is correct
15 Correct 45 ms 10112 KB Output is correct
16 Correct 37 ms 8120 KB Output is correct
17 Correct 37 ms 7436 KB Output is correct
18 Correct 14 ms 4276 KB Output is correct
19 Correct 41 ms 9932 KB Output is correct
20 Correct 44 ms 10060 KB Output is correct
21 Correct 37 ms 8140 KB Output is correct
22 Correct 37 ms 7476 KB Output is correct
23 Correct 45 ms 10856 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2004 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1972 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1852 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 7 ms 3448 KB Output is correct
12 Correct 14 ms 4544 KB Output is correct
13 Correct 31 ms 14872 KB Output is correct
14 Correct 46 ms 9952 KB Output is correct
15 Correct 45 ms 10112 KB Output is correct
16 Correct 37 ms 8120 KB Output is correct
17 Correct 37 ms 7436 KB Output is correct
18 Correct 14 ms 4276 KB Output is correct
19 Correct 41 ms 9932 KB Output is correct
20 Correct 44 ms 10060 KB Output is correct
21 Correct 37 ms 8140 KB Output is correct
22 Correct 37 ms 7476 KB Output is correct
23 Correct 45 ms 10856 KB Output is correct
24 Correct 2 ms 1864 KB Output is correct
25 Correct 115 ms 3452 KB Output is correct
26 Correct 133 ms 4600 KB Output is correct
27 Correct 3792 ms 14908 KB Output is correct
28 Correct 1240 ms 9920 KB Output is correct
29 Correct 3723 ms 10168 KB Output is correct
30 Correct 2302 ms 8292 KB Output is correct
31 Correct 2337 ms 7532 KB Output is correct
32 Correct 155 ms 4392 KB Output is correct
33 Correct 1316 ms 10060 KB Output is correct
34 Correct 3668 ms 10192 KB Output is correct
35 Correct 2304 ms 8160 KB Output is correct
36 Correct 2968 ms 7544 KB Output is correct
37 Correct 877 ms 11084 KB Output is correct
38 Correct 4048 ms 17848 KB Output is correct