oj.uz

Submission #559020

# Submission time Handle Problem Language Result Execution time Memory
559020 2022-05-09T08:34:26 Z ngpin04 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 38616 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();
    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 8 ms 14676 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 8 ms 14604 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 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 14548 KB Output is correct
9 Correct 10 ms 14860 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 9 ms 14548 KB Output is correct
3 Correct 8 ms 14604 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 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 14548 KB Output is correct
9 Correct 10 ms 14860 KB Output is correct
10 Correct 9 ms 14360 KB Output is correct
11 Correct 17 ms 17220 KB Output is correct
12 Correct 31 ms 19364 KB Output is correct
13 Correct 47 ms 38616 KB Output is correct
14 Correct 99 ms 27764 KB Output is correct
15 Correct 105 ms 28024 KB Output is correct
16 Correct 90 ms 25932 KB Output is correct
17 Correct 87 ms 24984 KB Output is correct
18 Correct 33 ms 19040 KB Output is correct
19 Correct 96 ms 27728 KB Output is correct
20 Correct 106 ms 28136 KB Output is correct
21 Correct 91 ms 25820 KB Output is correct
22 Correct 89 ms 25036 KB Output is correct
23 Correct 95 ms 29068 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 9 ms 14548 KB Output is correct
3 Correct 8 ms 14604 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 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 14548 KB Output is correct
9 Correct 10 ms 14860 KB Output is correct
10 Correct 9 ms 14360 KB Output is correct
11 Correct 17 ms 17220 KB Output is correct
12 Correct 31 ms 19364 KB Output is correct
13 Correct 47 ms 38616 KB Output is correct
14 Correct 99 ms 27764 KB Output is correct
15 Correct 105 ms 28024 KB Output is correct
16 Correct 90 ms 25932 KB Output is correct
17 Correct 87 ms 24984 KB Output is correct
18 Correct 33 ms 19040 KB Output is correct
19 Correct 96 ms 27728 KB Output is correct
20 Correct 106 ms 28136 KB Output is correct
21 Correct 91 ms 25820 KB Output is correct
22 Correct 89 ms 25036 KB Output is correct
23 Correct 95 ms 29068 KB Output is correct
24 Correct 11 ms 14396 KB Output is correct
25 Correct 1156 ms 17240 KB Output is correct
26 Execution timed out 5064 ms 19372 KB Time limit exceeded
27 Halted 0 ms 0 KB -