답안 #49787 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49787	2018-06-03T06:38:08 Z	gs13105	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	70 ms	13792 KB

garden

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

void answer(int x);

const int MAXN = 150000;
const int MAXN2 = MAXN * 2;

int arr[MAXN2 + 10];
int dis[2][MAXN2 + 10];
bool chk[2][MAXN2 + 10];

void f(int x, int p)
{
    //assert(!chk[p % 2][x]);
    chk[p % 2][x] = 1;
    if(arr[x] == p)
    {
        //assert(!dis[p % 2][x]);
        dis[p % 2][x] = 1;
        return;
    }

    if(!chk[p % 2][arr[x]])
        f(arr[x], p);

    //assert(!dis[p % 2][x]);
    if(dis[p % 2][arr[x]])
        dis[p % 2][x] = dis[p % 2][arr[x]] + 1;
}

int mem1[MAXN + 10];
int mem2[MAXN + 10];
int sum[2][MAXN2 + 10];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    memset(mem1, -1, sizeof mem1);
    memset(mem2, -1, sizeof mem2);
    memset(arr, -1, sizeof arr);
    for(int i = 0; i < M; i++)
    {
        int x = R[i][0];
        int y = R[i][1];

        if(mem1[x] == -1)
            mem1[x] = y;
        else if(mem2[x] == -1)
            mem2[x] = y;

        if(mem1[y] == -1)
            mem1[y] = x;
        else if(mem2[y] == -1)
            mem2[y] = x;
    }

    for(int i = 0; i < N; i++)
    {
        //assert(mem1[i] != -1);
        if(mem1[mem1[i]] == i && mem2[mem1[i]] != -1)
            arr[2 * i] = 2 * mem1[i] + 1;
        else
            arr[2 * i] = 2 * mem1[i];

        if(mem2[i] != -1)
        {
            if(mem1[mem2[i]] == i && mem2[mem2[i]] != -1)
                arr[2 * i + 1] = 2 * mem2[i] + 1;
            else
                arr[2 * i + 1] = 2 * mem2[i];
        }
    }

    for(int r = 0; r < 2; r++)
        for(int i = 0; i < 2 * N; i++)
            if(!chk[r][i] && arr[i] != -1)
                f(i, 2 * P + r);

    for(int r = 0; r < 2; r++)
        for(int i = 0; i < N; i++)
            if(dis[r][2 * i])
                /*assert(dis[r][2 * i] <= 2 * N), */sum[r][dis[r][2 * i]]++;

    for(int r = 0; r < 2; r++)
    {
        int c = dis[r][2 * P + r];
        if(!c)
            continue;

        for(int i = 1; i <= 2 * N; i++)
            if(i - c >= 1)
                sum[r][i] += sum[r][i - c];
    }

    //assert(dis[0][2 * P] == 0 || dis[1][2 * P + 1] == 0 || dis[0][2 * P] == dis[1][2 * P + 1]);
    //int c = max(dis[0][2 * P], dis[1][2 * P + 1]);
    int c1 = dis[0][2 * P];
    int c2 = dis[1][2 * P + 1];
    if(c1 == 0)
        c1 = c2;
    if(c2 == 0)
        c2 = c1;
    for(int i = 0; i < Q; i++)
    {
        int r = 0;
        {
            int t = G[i];
            if(t > 2 * N && c1)
                t -= ((t - 2 * N + c1 - 1) / c1) * c1;

            if(t <= 2 * N)
                r += sum[0][t];
        }
        {
            int t = G[i];
            if(t > 2 * N && c2)
                t -= ((t - 2 * N + c2 - 1) / c2) * c2;

            if(t <= 2 * N)
                r += sum[1][t];
        }
        answer(r);
    }
}

Subtask #1
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2804 KB	Output is correct
2	Correct	4 ms	2836 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	5 ms	2680 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	4 ms	2680 KB	Output is correct
8	Correct	5 ms	2732 KB	Output is correct
9	Correct	6 ms	2908 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2804 KB	Output is correct
2	Correct	4 ms	2836 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	5 ms	2680 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	4 ms	2680 KB	Output is correct
8	Correct	5 ms	2732 KB	Output is correct
9	Correct	6 ms	2908 KB	Output is correct
10	Correct	4 ms	2680 KB	Output is correct
11	Correct	11 ms	3832 KB	Output is correct
12	Correct	21 ms	4432 KB	Output is correct
13	Correct	37 ms	11196 KB	Output is correct
14	Correct	58 ms	7956 KB	Output is correct
15	Correct	61 ms	8672 KB	Output is correct
16	Correct	52 ms	6592 KB	Output is correct
17	Correct	52 ms	5956 KB	Output is correct
18	Correct	21 ms	3720 KB	Output is correct
19	Correct	58 ms	8564 KB	Output is correct
20	Correct	63 ms	8748 KB	Output is correct
21	Correct	52 ms	5696 KB	Output is correct
22	Correct	53 ms	6620 KB	Output is correct
23	Correct	58 ms	9588 KB	Output is correct

Subtask #3
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2804 KB	Output is correct
2	Correct	4 ms	2836 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	5 ms	2680 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	4 ms	2680 KB	Output is correct
8	Correct	5 ms	2732 KB	Output is correct
9	Correct	6 ms	2908 KB	Output is correct
10	Correct	4 ms	2680 KB	Output is correct
11	Correct	11 ms	3832 KB	Output is correct
12	Correct	21 ms	4432 KB	Output is correct
13	Correct	37 ms	11196 KB	Output is correct
14	Correct	58 ms	7956 KB	Output is correct
15	Correct	61 ms	8672 KB	Output is correct
16	Correct	52 ms	6592 KB	Output is correct
17	Correct	52 ms	5956 KB	Output is correct
18	Correct	21 ms	3720 KB	Output is correct
19	Correct	58 ms	8564 KB	Output is correct
20	Correct	63 ms	8748 KB	Output is correct
21	Correct	52 ms	5696 KB	Output is correct
22	Correct	53 ms	6620 KB	Output is correct
23	Correct	58 ms	9588 KB	Output is correct
24	Correct	5 ms	2808 KB	Output is correct
25	Correct	12 ms	3760 KB	Output is correct
26	Correct	22 ms	4924 KB	Output is correct
27	Correct	38 ms	11784 KB	Output is correct
28	Correct	59 ms	9508 KB	Output is correct
29	Correct	60 ms	9164 KB	Output is correct
30	Correct	53 ms	7124 KB	Output is correct
31	Correct	52 ms	6440 KB	Output is correct
32	Correct	23 ms	4188 KB	Output is correct
33	Correct	57 ms	8564 KB	Output is correct
34	Correct	60 ms	9160 KB	Output is correct
35	Correct	53 ms	6400 KB	Output is correct
36	Correct	53 ms	6388 KB	Output is correct
37	Correct	58 ms	8624 KB	Output is correct
38	Correct	70 ms	13792 KB	Output is correct

답안 #49787

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