oj.uz

Submission #559023

# Submission time Handle Problem Language Result Execution time Memory
559023 2022-05-09T08:51:23 Z ngpin04 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 38612 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
const int Nmax = 3e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"

vector <int> adj[Nmax];
vector <int> vt[Nmax];

pair <int, int> ed[Nmax];
pair <int, int> mn[Nmax];

int ptr[Nmax];
int s[Nmax];
int h[Nmax];
int n,m,p,q,cnt,sz;

bool flag[Nmax];
bool vis[Nmax];
bool ins[Nmax];
bool cyc[Nmax];
bool ok[Nmax];

void dfs(int i) {
    if (ins[i]) {
        cnt++;
        int j;
        do {
            j = s[sz];
            sz--;
            cyc[j] = true;
            ins[j] = false;
            vt[cnt].push_back(j);
        } while (j != i);
        reverse(ALL(vt[cnt]));
        return;
    }
    if (vis[i])
        return;

    vis[i] = true;
    ins[i] = true;
    s[++sz] = i;
    dfs(ptr[i]);

    if (ins[i]) {
        ins[i] = false;
        sz--;
    }
}

void build() {
    m <<= 1;
    for (int i = 0; i < n; i++)
        mn[i] = mp(oo, oo);

    for (int i = 0; i < m; i++) {
        int u = ed[i].fi;
        if (!mini(mn[u].fi, i))
            mini(mn[u].se, i);
    }

    for (int i = 0; i < m; i++) {
        int u = ed[i].fi;
        int v = ed[i].se;
        if (mn[v].fi == (i ^ 1)) {
            if (mn[v].se == oo)
                ptr[i] = (i ^ 1);
            else
                ptr[i] = mn[v].se; 
        } else {
            ptr[i] = mn[v].fi;
        }
    }

    for (int i = 0; i < m; i++) if (!vis[i]) {
        sz = 0;
        dfs(i);
    }

    for (int i = 0; i < m; i++) 
        adj[ptr[i]].push_back(i);

    for (int i = 0; i < n; i++)
        flag[mn[i].fi] = true;
}

void solve(int u, vector <int> &vt, int cur, int k) {
    if (cur < 0)
        cur = (int) vt.size() - 1;

    s[++sz] = u;
    if (flag[u]) {
        if (sz > k) {
            int v = s[sz - k];
            if (ed[v].se == p)
                ok[u] = true;
        } else {
            int v = vt[cur];
            if (ed[v].se == p)
                ok[u] = true;
        }
    }

    for (int v : adj[u]) 
        if (!cyc[v]) 
            solve(v, vt, cur - 1, k);

    sz--;
}

int solve(int k) {
    for (int i = 0; i < m; i++)
        ok[i] = false;

    k--;
    for (int i = 1; i <= cnt; i++) 
    for (int j = 0, cur = k % (int) vt[i].size(); j < (int) vt[i].size(); j++) {
        solve(vt[i][j], vt[i], cur, k);
        cur++;
        if (cur == (int) vt[i].size())
            cur = 0;
    }

    int res = 0;
    for (int i = 0; i < n; i++)
        res += ok[mn[i].fi];

    return res;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for (int i = 0; i < M; i++)
    for (int j = 0; j < 2; j++)
        ed[i << 1 | j] = mp(R[i][j], R[i][j ^ 1]);

    n = N;
    m = M;
    p = P;
    q = Q;

    build();
    for (int i = 0; i < q; i++) 
        answer(solve(G[i]));
}

Compilation message

garden.cpp: In function 'void build()':
garden.cpp:81:13: warning: unused variable 'u' [-Wunused-variable]
   81 |         int u = ed[i].fi;
      |             ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 7 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14480 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 13 ms 14956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 7 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14480 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 13 ms 14956 KB Output is correct
10 Correct 10 ms 14420 KB Output is correct
11 Correct 19 ms 17144 KB Output is correct
12 Correct 42 ms 19252 KB Output is correct
13 Correct 43 ms 38612 KB Output is correct
14 Correct 96 ms 27712 KB Output is correct
15 Correct 122 ms 28272 KB Output is correct
16 Correct 129 ms 26028 KB Output is correct
17 Correct 85 ms 24908 KB Output is correct
18 Correct 32 ms 19028 KB Output is correct
19 Correct 95 ms 27576 KB Output is correct
20 Correct 110 ms 28148 KB Output is correct
21 Correct 123 ms 26044 KB Output is correct
22 Correct 106 ms 25108 KB Output is correct
23 Correct 117 ms 29100 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 7 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14480 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 13 ms 14956 KB Output is correct
10 Correct 10 ms 14420 KB Output is correct
11 Correct 19 ms 17144 KB Output is correct
12 Correct 42 ms 19252 KB Output is correct
13 Correct 43 ms 38612 KB Output is correct
14 Correct 96 ms 27712 KB Output is correct
15 Correct 122 ms 28272 KB Output is correct
16 Correct 129 ms 26028 KB Output is correct
17 Correct 85 ms 24908 KB Output is correct
18 Correct 32 ms 19028 KB Output is correct
19 Correct 95 ms 27576 KB Output is correct
20 Correct 110 ms 28148 KB Output is correct
21 Correct 123 ms 26044 KB Output is correct
22 Correct 106 ms 25108 KB Output is correct
23 Correct 117 ms 29100 KB Output is correct
24 Correct 12 ms 14420 KB Output is correct
25 Correct 1134 ms 17368 KB Output is correct
26 Execution timed out 5040 ms 19364 KB Time limit exceeded
27 Halted 0 ms 0 KB -