답안 #50968 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50968	2018-06-15T10:06:46 Z	aquablitz11	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	2785 ms	45892 KB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

const int N = 150010;
const int INF = 1e9;

vector<int> mn[N], G[2*N];
int nxt[2*N], deg[2*N], h[2*N][3], ph[2*N][3];
bool comp[2*N][3];

void expand(int u, int c, int s, int d=0, int p=-INF)
{
    if (comp[u][c])
        return;
    if (deg[u] == 0 && (u == 2*s || u == 2*s+1)) {
        //assert(p < 0);
        p = 0;
    }
    h[u][c] = d, ph[u][c] = p;
    comp[u][c] = true;
    for (auto v : G[u])
        expand(v, c, s, d+1, p+1);
}

void count_routes(int n, int m, int p, int R[][2], int q, int K[])
{
    // find min and second-min
    for (int i = 0; i < m; ++i) {
        int u = R[i][0], v = R[i][1];
        if (mn[u].size() < 2)
            mn[u].push_back(v);
        if (mn[v].size() < 2)
            mn[v].push_back(u);
    }

    // completely fill second-min
    for (int i = 0; i < n; ++i) {
        if (mn[i].size() == 0) continue;
        if (mn[i].size() == 1) mn[i].push_back(mn[i].back());
    }

    // find nxt of each node
    for (int i = 0; i < n; ++i) {
        nxt[2*i] = nxt[2*i+1] = -1;
        if (mn[i].size() == 0) continue;
        // normal node
        int j = mn[i][0];
        if (mn[j][0] != i) nxt[2*i] = 2*j;
        else nxt[2*i] = 2*j+1;
        // walked node
        j = mn[i][1];
        if (mn[j][0] != i) nxt[2*i+1] = 2*j;
        else nxt[2*i+1] = 2*j+1;
    }

    // find degree and make reversed graph: G
    for (int u = 0; u < 2*n; ++u) {
        if (nxt[u] == -1) continue;
        ++deg[nxt[u]];
        G[nxt[u]].push_back(u);
    }

    // find cycle
    queue<int> Q;
    for (int u = 0; u < 2*n; ++u) {
        if (nxt[u] != -1 && deg[u] == 0)
            Q.push(u);
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        if (--deg[nxt[u]] == 0)
            Q.push(nxt[u]);
    }
    //for (int u = 0; u < 2*n; ++u)
        //assert(deg[u] == 0 || deg[u] == 1);

    // expand
    expand(2*p, 1, p);
    expand(2*p+1, 2, p);

    // find cycle size for 2*p and 2*p+1 (just in case they're different)
    int c1 = 0, u = 2*p;
    if (deg[u] == 1) {
        do {
            ++c1;
            u = nxt[u];
        } while (u != 2*p);
    }

    int c2 = 0;
    u = 2*p+1;
    if (deg[u] == 1) {
        do {
            ++c2;
            u = nxt[u];
        } while (u != 2*p+1);
    }

    //assert(c1 == 0 || c2 == 0 || c1 == c2);

    // answer each query
    for (int i = 0; i < q; ++i) {
        int k = K[i], cnt = 0;
        for (int u = 0; u < 2*n; u += 2) {
            if (nxt[u] == -1) continue;
            bool ans = false;
            if (comp[u][1]) {
                ans |= ph[u][1] == k;
                ans |= c1 > 0 && k-h[u][1] >= 0 && (k-h[u][1])%c1 == 0;
            }
            if (comp[u][2]) {
                ans |= ph[u][2] == k;
                ans |= c2 > 0 && k-h[u][2] >= 0 && (k-h[u][2])%c2 == 0;
            }
            if (ans) ++cnt;
        }
        answer(cnt);
    }

}

Subtask #1
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	11216 KB	Output is correct
2	Correct	13 ms	11100 KB	Output is correct
3	Correct	12 ms	11100 KB	Output is correct
4	Correct	12 ms	10880 KB	Output is correct
5	Correct	14 ms	10988 KB	Output is correct
6	Correct	13 ms	11288 KB	Output is correct
7	Correct	12 ms	10912 KB	Output is correct
8	Correct	12 ms	11100 KB	Output is correct
9	Correct	14 ms	11120 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	11216 KB	Output is correct
2	Correct	13 ms	11100 KB	Output is correct
3	Correct	12 ms	11100 KB	Output is correct
4	Correct	12 ms	10880 KB	Output is correct
5	Correct	14 ms	10988 KB	Output is correct
6	Correct	13 ms	11288 KB	Output is correct
7	Correct	12 ms	10912 KB	Output is correct
8	Correct	12 ms	11100 KB	Output is correct
9	Correct	14 ms	11120 KB	Output is correct
10	Correct	11 ms	10920 KB	Output is correct
11	Correct	25 ms	13816 KB	Output is correct
12	Correct	46 ms	16244 KB	Output is correct
13	Correct	80 ms	36148 KB	Output is correct
14	Correct	158 ms	30572 KB	Output is correct
15	Correct	188 ms	30940 KB	Output is correct
16	Correct	140 ms	25840 KB	Output is correct
17	Correct	124 ms	22812 KB	Output is correct
18	Correct	49 ms	16860 KB	Output is correct
19	Correct	151 ms	31768 KB	Output is correct
20	Correct	202 ms	31444 KB	Output is correct
21	Correct	130 ms	24872 KB	Output is correct
22	Correct	124 ms	22784 KB	Output is correct
23	Correct	168 ms	33472 KB	Output is correct

Subtask #3
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	11216 KB	Output is correct
2	Correct	13 ms	11100 KB	Output is correct
3	Correct	12 ms	11100 KB	Output is correct
4	Correct	12 ms	10880 KB	Output is correct
5	Correct	14 ms	10988 KB	Output is correct
6	Correct	13 ms	11288 KB	Output is correct
7	Correct	12 ms	10912 KB	Output is correct
8	Correct	12 ms	11100 KB	Output is correct
9	Correct	14 ms	11120 KB	Output is correct
10	Correct	11 ms	10920 KB	Output is correct
11	Correct	25 ms	13816 KB	Output is correct
12	Correct	46 ms	16244 KB	Output is correct
13	Correct	80 ms	36148 KB	Output is correct
14	Correct	158 ms	30572 KB	Output is correct
15	Correct	188 ms	30940 KB	Output is correct
16	Correct	140 ms	25840 KB	Output is correct
17	Correct	124 ms	22812 KB	Output is correct
18	Correct	49 ms	16860 KB	Output is correct
19	Correct	151 ms	31768 KB	Output is correct
20	Correct	202 ms	31444 KB	Output is correct
21	Correct	130 ms	24872 KB	Output is correct
22	Correct	124 ms	22784 KB	Output is correct
23	Correct	168 ms	33472 KB	Output is correct
24	Correct	13 ms	11000 KB	Output is correct
25	Correct	135 ms	14152 KB	Output is correct
26	Correct	188 ms	16940 KB	Output is correct
27	Correct	1663 ms	37132 KB	Output is correct
28	Correct	1417 ms	32364 KB	Output is correct
29	Correct	2086 ms	32512 KB	Output is correct
30	Correct	1129 ms	26608 KB	Output is correct
31	Correct	1206 ms	24488 KB	Output is correct
32	Correct	200 ms	17144 KB	Output is correct
33	Correct	1410 ms	32188 KB	Output is correct
34	Correct	1941 ms	32496 KB	Output is correct
35	Correct	1133 ms	26476 KB	Output is correct
36	Correct	1729 ms	24392 KB	Output is correct
37	Correct	1128 ms	33536 KB	Output is correct
38	Correct	2785 ms	45892 KB	Output is correct

답안 #50968

Compilation message

Subtask #1 49.0 / 49.0

Subtask #2 20.0 / 20.0

Subtask #3 31.0 / 31.0

Subtask #1
49.0 / 49.0

Subtask #2
20.0 / 20.0

Subtask #3
31.0 / 31.0