oj.uz

Submission #559265

# Submission time Handle Problem Language Result Execution time Memory
559265 2022-05-09T14:49:22 Z ngpin04 Tropical Garden (IOI11_garden) C++14
49 / 100
 96 ms 44884 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> val[Nmax];

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

int ptr[Nmax];
int ans[Nmax];
int qr[Nmax];
int n,m,p,q;

bool cyc[Nmax];

void addEdge(int u, int v) {
    // cerr << u << " " << v << "\n";
    ptr[u] = v;
    adj[v].push_back(u);
}

void build() {
    for (int i = 0; i < n; i++)
        pir[i] = mp(-1, -1);

    for (int i = 0; i < m; i++) {
        int u = ed[i].fi;
        int v = ed[i].se;

        if (pir[u].fi == -1)
            pir[u].fi = v;
        else if (pir[u].se == -1)
            pir[u].se = v;

        if (pir[v].fi == -1)
            pir[v].fi = u;
        else if (pir[v].se == -1)
            pir[v].se = u;        
    }

    for (int i = 0; i < n; i++) {
        int j;
        j = pir[i].fi;
        if (pir[j].fi == i)
            addEdge(i, j + n);
        else
            addEdge(i, j);

        j = pir[i].se;
        if (j == -1) {
            addEdge(i + n, ptr[i]);
        } else {
            if (pir[j].fi == i)
                addEdge(i + n, j + n);
            else
                addEdge(i + n, j);
        }
    }
}

void dfs(int u, int d, vector <int> &cnt) {
    if (u < n)
        cnt[d]++;
    for (int v : adj[u]) 
        dfs(v, d + 1, cnt);
}

void dfs1(int u, int d, int sz) {
    if (u < n)
        val[d % sz].push_back(d);
    for (int v : adj[u])
        if (!cyc[v])
            dfs1(v, d + 1, sz);
}

void solve(int s) {
    memset(cyc, 0, sizeof(cyc));
    int v = s;
    int sz = 0;
    while (!cyc[ptr[v]]) {
        v = ptr[v];
        cyc[v] = true;
        sz++;
    }

    for (int i = 0; i < sz; i++)
        val[i].clear();
    
    if (v != s) {
        vector <int> cnt(2 * n, 0);
        dfs(s, 0, cnt);

        for (int i = 0; i < q; i++)
            ans[i] += cnt[qr[i]];
    } else {
        for (int v = s, rep = 1, cur = 0; rep <= sz; v = ptr[v], rep++) {
            dfs1(v, cur, sz);

            cur--;
            if (cur < 0)
                cur = sz - 1;
        }
        for (int i = 0; i < sz; i++)
            sort(ALL(val[i]));

        for (int i = 0; i < q; i++) {
            int k = qr[i];
            int v = k % sz;
            ans[i] += upper_bound(ALL(val[v]), k) - val[v].begin();
        }
    }


}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    m = M;
    p = P;
    q = Q;
    for (int i = 0; i < m; i++)
        ed[i] = mp(R[i][0], R[i][1]);
    for (int i = 0; i < q; i++)
        qr[i] = G[i];

    build();
    solve(p);
    solve(p + n);

    for (int i = 0; i < q; i++)
        answer(ans[i]);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14804 KB Output is correct
2 Correct 11 ms 14792 KB Output is correct
3 Correct 12 ms 14804 KB Output is correct
4 Correct 10 ms 14676 KB Output is correct
5 Correct 9 ms 14676 KB Output is correct
6 Correct 11 ms 14992 KB Output is correct
7 Correct 10 ms 14656 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 14 ms 14932 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14804 KB Output is correct
2 Correct 11 ms 14792 KB Output is correct
3 Correct 12 ms 14804 KB Output is correct
4 Correct 10 ms 14676 KB Output is correct
5 Correct 9 ms 14676 KB Output is correct
6 Correct 11 ms 14992 KB Output is correct
7 Correct 10 ms 14656 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 14 ms 14932 KB Output is correct
10 Correct 10 ms 14692 KB Output is correct
11 Correct 21 ms 16596 KB Output is correct
12 Correct 28 ms 18060 KB Output is correct
13 Correct 51 ms 26328 KB Output is correct
14 Correct 77 ms 25416 KB Output is correct
15 Correct 96 ms 26160 KB Output is correct
16 Correct 77 ms 23820 KB Output is correct
17 Runtime error 78 ms 44884 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14804 KB Output is correct
2 Correct 11 ms 14792 KB Output is correct
3 Correct 12 ms 14804 KB Output is correct
4 Correct 10 ms 14676 KB Output is correct
5 Correct 9 ms 14676 KB Output is correct
6 Correct 11 ms 14992 KB Output is correct
7 Correct 10 ms 14656 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 14 ms 14932 KB Output is correct
10 Correct 10 ms 14692 KB Output is correct
11 Correct 21 ms 16596 KB Output is correct
12 Correct 28 ms 18060 KB Output is correct
13 Correct 51 ms 26328 KB Output is correct
14 Correct 77 ms 25416 KB Output is correct
15 Correct 96 ms 26160 KB Output is correct
16 Correct 77 ms 23820 KB Output is correct
17 Runtime error 78 ms 44884 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -