oj.uz

Submission #559018

# Submission time Handle Problem Language Result Execution time Memory
559018 2022-05-09T08:29:54 Z ngpin04 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 38524 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 &ind, int &k) {
    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[(ind + k - (sz - 1)) % vt.size()];
            if (ed[v].se == p)
                ok[u] = true;
        }
    }

    for (int v : adj[u]) 
        if (!cyc[v]) 
            solve(v, vt, ind, 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; j < (int) vt[i].size(); j++)
        solve(vt[i][j], vt[i], j, k);

    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 14720 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14472 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14436 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14880 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14720 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14472 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14436 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14880 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 19 ms 17212 KB Output is correct
12 Correct 35 ms 19292 KB Output is correct
13 Correct 49 ms 38524 KB Output is correct
14 Correct 111 ms 27704 KB Output is correct
15 Correct 110 ms 28136 KB Output is correct
16 Correct 109 ms 26032 KB Output is correct
17 Correct 93 ms 24960 KB Output is correct
18 Correct 40 ms 19032 KB Output is correct
19 Correct 110 ms 27632 KB Output is correct
20 Correct 104 ms 28024 KB Output is correct
21 Correct 97 ms 26044 KB Output is correct
22 Correct 90 ms 25108 KB Output is correct
23 Correct 123 ms 29156 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14720 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14472 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14436 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 10 ms 14880 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 19 ms 17212 KB Output is correct
12 Correct 35 ms 19292 KB Output is correct
13 Correct 49 ms 38524 KB Output is correct
14 Correct 111 ms 27704 KB Output is correct
15 Correct 110 ms 28136 KB Output is correct
16 Correct 109 ms 26032 KB Output is correct
17 Correct 93 ms 24960 KB Output is correct
18 Correct 40 ms 19032 KB Output is correct
19 Correct 110 ms 27632 KB Output is correct
20 Correct 104 ms 28024 KB Output is correct
21 Correct 97 ms 26044 KB Output is correct
22 Correct 90 ms 25108 KB Output is correct
23 Correct 123 ms 29156 KB Output is correct
24 Correct 11 ms 14420 KB Output is correct
25 Correct 1183 ms 17244 KB Output is correct
26 Execution timed out 5060 ms 19376 KB Time limit exceeded
27 Halted 0 ms 0 KB -