oj.uz

Submission #559021

# Submission time Handle Problem Language Result Execution time Memory
559021 2022-05-09T08:35:29 Z ngpin04 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 38608 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];
vector <int> s;

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

int anc[Nmax][20];
int ptr[Nmax];
int h[Nmax];
int n,m,p,q,cnt;

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.back();
            s.pop_back();
            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.push_back(i);
    dfs(ptr[i]);

    if (ins[i]) {
        ins[i] = false;
        s.pop_back();
    }
}

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;
        int v = ed[i].se;
        mini(mn[u].se, i);
        if (mn[u].se < mn[u].fi)
            swap(mn[u].fi, mn[u].se);
    }

    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]) {
        s.clear();
        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.push_back(u);

    int sz = s.size();
    if (flag[u]) {
        if (sz > k) {
            int v = s[sz - k - 1];
            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);

    s.pop_back();
}

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();
    if (N * Q >= 1e8)
        return;
    for (int i = 0; i < q; i++) 
        answer(solve(G[i]));
}

Compilation message

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Correct 8 ms 14488 KB Output is correct
3 Correct 9 ms 14600 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 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 10 ms 14948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Correct 8 ms 14488 KB Output is correct
3 Correct 9 ms 14600 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 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 10 ms 14948 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 16 ms 17236 KB Output is correct
12 Correct 29 ms 19276 KB Output is correct
13 Correct 51 ms 38608 KB Output is correct
14 Correct 94 ms 27676 KB Output is correct
15 Correct 114 ms 28064 KB Output is correct
16 Correct 92 ms 26004 KB Output is correct
17 Correct 86 ms 25132 KB Output is correct
18 Correct 38 ms 19148 KB Output is correct
19 Correct 97 ms 27616 KB Output is correct
20 Correct 111 ms 28044 KB Output is correct
21 Correct 104 ms 25812 KB Output is correct
22 Correct 88 ms 25104 KB Output is correct
23 Correct 95 ms 29104 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Correct 8 ms 14488 KB Output is correct
3 Correct 9 ms 14600 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 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 10 ms 14948 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 16 ms 17236 KB Output is correct
12 Correct 29 ms 19276 KB Output is correct
13 Correct 51 ms 38608 KB Output is correct
14 Correct 94 ms 27676 KB Output is correct
15 Correct 114 ms 28064 KB Output is correct
16 Correct 92 ms 26004 KB Output is correct
17 Correct 86 ms 25132 KB Output is correct
18 Correct 38 ms 19148 KB Output is correct
19 Correct 97 ms 27616 KB Output is correct
20 Correct 111 ms 28044 KB Output is correct
21 Correct 104 ms 25812 KB Output is correct
22 Correct 88 ms 25104 KB Output is correct
23 Correct 95 ms 29104 KB Output is correct
24 Correct 12 ms 14436 KB Output is correct
25 Correct 1171 ms 17244 KB Output is correct
26 Execution timed out 5050 ms 19376 KB Time limit exceeded
27 Halted 0 ms 0 KB -