oj.uz

Submission #559016

# Submission time Handle Problem Language Result Execution time Memory
559016 2022-05-09T08:17:56 Z ngpin04 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 39364 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 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);
}

void solve(int u, vector <int> &vt, int ind, int k) {
    s.push_back(u);

    int sz = s.size();
    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:76:13: warning: unused variable 'v' [-Wunused-variable]
   76 |         int v = ed[i].se;
      |             ^
garden.cpp:83:13: warning: unused variable 'u' [-Wunused-variable]
   83 |         int u = ed[i].fi;
      |             ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14636 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 8 ms 14600 KB Output is correct
4 Correct 8 ms 14388 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14684 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 11 ms 14932 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14636 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 8 ms 14600 KB Output is correct
4 Correct 8 ms 14388 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14684 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 11 ms 14932 KB Output is correct
10 Correct 9 ms 14444 KB Output is correct
11 Correct 15 ms 17448 KB Output is correct
12 Correct 34 ms 19788 KB Output is correct
13 Correct 44 ms 39364 KB Output is correct
14 Correct 107 ms 29004 KB Output is correct
15 Correct 109 ms 29540 KB Output is correct
16 Correct 90 ms 27336 KB Output is correct
17 Correct 86 ms 26380 KB Output is correct
18 Correct 36 ms 19468 KB Output is correct
19 Correct 100 ms 29292 KB Output is correct
20 Correct 104 ms 29516 KB Output is correct
21 Correct 95 ms 27240 KB Output is correct
22 Correct 89 ms 26344 KB Output is correct
23 Correct 96 ms 30540 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14636 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 8 ms 14600 KB Output is correct
4 Correct 8 ms 14388 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14684 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 11 ms 14932 KB Output is correct
10 Correct 9 ms 14444 KB Output is correct
11 Correct 15 ms 17448 KB Output is correct
12 Correct 34 ms 19788 KB Output is correct
13 Correct 44 ms 39364 KB Output is correct
14 Correct 107 ms 29004 KB Output is correct
15 Correct 109 ms 29540 KB Output is correct
16 Correct 90 ms 27336 KB Output is correct
17 Correct 86 ms 26380 KB Output is correct
18 Correct 36 ms 19468 KB Output is correct
19 Correct 100 ms 29292 KB Output is correct
20 Correct 104 ms 29516 KB Output is correct
21 Correct 95 ms 27240 KB Output is correct
22 Correct 89 ms 26344 KB Output is correct
23 Correct 96 ms 30540 KB Output is correct
24 Correct 12 ms 14508 KB Output is correct
25 Correct 1195 ms 17584 KB Output is correct
26 Execution timed out 5039 ms 19884 KB Time limit exceeded
27 Halted 0 ms 0 KB -