oj.uz

Submission #1029110

# Submission time Handle Problem Language Result Execution time Memory
1029110 2024-07-20T12:34:23 Z idas Tropical Garden (IOI11_garden) C++11
100 / 100
 1247 ms 35604 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;

const int MxN=150001, INF=1e9;
int mn[2*MxN], mx[2*MxN], nxt[2*MxN], dist[2*MxN][2], cyc[2];
vi prv[2*MxN];
bool v[2*MxN];

int cyc_find(int u, int st)
{
    if(v[u]){
        if(u==st) return 0;
        else return -1;
    }
    v[u]=true;
    int x=nxt[u];
    int k=cyc_find(x, st);
    if(k==-1) return -1;
    else return k+1;
}

void calc_dist(int u, int in)
{
    for(auto x : prv[u]){
        if(dist[x][in]==-1){
            dist[x][in]=dist[u][in]+1;
            calc_dist(x, in);
        }
    }
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
    FOR(i, 0, n)
    {
        mn[i]=mn[i+n]=-1;
        mx[i]=mx[i+n]=-1;
        nxt[i]=nxt[i+n]=-1;
    }

    FOR(i, 0, m)
    {
        int a=r[i][0], b=r[i][1];

        if(mn[a]==-1) mn[a]=mn[a+n]=b;
        else if(mx[a]==-1) mx[a]=mx[a+n]=b;

        if(mn[b]==-1) mn[b]=mn[b+n]=a;
        else if(mx[b]==-1) mx[b]=mx[b+n]=a;
    }

    FOR(i, 0, n)
    {
        int x=mn[i];
        if(mx[x]==-1){
            nxt[i]=x;
        }
        else if(mn[x]==i){
            nxt[i]=x+n;
        }
        else{
            nxt[i]=x;
        }
    }

    FOR(i, n, 2*n)
    {
        if(mx[i]==-1) continue;

        int x=mx[i];
        if(mx[x]==-1){
            nxt[i]=x;
        }
        else if(mn[x]==i-n){
            nxt[i]=x+n;
        }
        else{
            nxt[i]=x;
        }
    }

    FOR(i, 0, 2*n)
    {
        dist[i][0]=dist[i][1]=-1;
        if(nxt[i]!=-1) prv[nxt[i]].pb(i);
    }

    cyc[0]=cyc_find(p, p);
    FOR(i, 0, 2*n) v[i]=false;
    cyc[1]=cyc_find(p+n, p+n);

    dist[p][0]=0; calc_dist(p, 0);
    dist[p+n][1]=0; calc_dist(p+n, 1);

    FOR(i, 0, q)
    {
        int ans=0;
        FOR(j, 0, n)
        {
            FOR(k, 0, 2)
            if(dist[j][k]!=-1){
                if(cyc[k]==-1){
                    if(dist[j][k]==g[i]) ans++;
                }
                else if(g[i]>=dist[j][k] && (g[i]-dist[j][k])%cyc[k]==0) ans++;
            }
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 7 ms 9820 KB Output is correct
12 Correct 15 ms 11364 KB Output is correct
13 Correct 31 ms 28496 KB Output is correct
14 Correct 34 ms 20056 KB Output is correct
15 Correct 45 ms 20388 KB Output is correct
16 Correct 33 ms 17324 KB Output is correct
17 Correct 37 ms 16228 KB Output is correct
18 Correct 22 ms 11356 KB Output is correct
19 Correct 36 ms 20052 KB Output is correct
20 Correct 45 ms 20304 KB Output is correct
21 Correct 45 ms 18268 KB Output is correct
22 Correct 37 ms 17232 KB Output is correct
23 Correct 36 ms 21584 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 4 ms 7516 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 7 ms 9820 KB Output is correct
12 Correct 15 ms 11364 KB Output is correct
13 Correct 31 ms 28496 KB Output is correct
14 Correct 34 ms 20056 KB Output is correct
15 Correct 45 ms 20388 KB Output is correct
16 Correct 33 ms 17324 KB Output is correct
17 Correct 37 ms 16228 KB Output is correct
18 Correct 22 ms 11356 KB Output is correct
19 Correct 36 ms 20052 KB Output is correct
20 Correct 45 ms 20304 KB Output is correct
21 Correct 45 ms 18268 KB Output is correct
22 Correct 37 ms 17232 KB Output is correct
23 Correct 36 ms 21584 KB Output is correct
24 Correct 2 ms 10588 KB Output is correct
25 Correct 86 ms 12528 KB Output is correct
26 Correct 154 ms 13408 KB Output is correct
27 Correct 679 ms 29780 KB Output is correct
28 Correct 785 ms 20668 KB Output is correct
29 Correct 582 ms 20836 KB Output is correct
30 Correct 409 ms 18000 KB Output is correct
31 Correct 428 ms 17060 KB Output is correct
32 Correct 148 ms 13844 KB Output is correct
33 Correct 785 ms 20604 KB Output is correct
34 Correct 550 ms 20820 KB Output is correct
35 Correct 390 ms 18088 KB Output is correct
36 Correct 728 ms 16988 KB Output is correct
37 Correct 638 ms 21596 KB Output is correct
38 Correct 1247 ms 35604 KB Output is correct