oj.uz

답안 #999365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
999365 2024-06-15T11:17:50 Z popu 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
100 / 100
 1392 ms 35668 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

vector<vector<int>> graf, auxgraf;
int p, n, m, v1[300005], v2[300005], c, cycle1, cycle2;

void afis()
{
    for(int i = 0; i < 2 * n; i++)
    {
        if(i % 2)
            cout << i / 2 << "' : ";
        else
            cout << i / 2 << " : ";
        if(graf[i].size())
        {
            if(graf[i][0] % 2)
                cout << graf[i][0] / 2 << "'";
            else
                cout << graf[i][0] / 2;
        }
        cout << '\n';
    }
    cout << '\n';
}

int dfs1(int node)
{
    if(!v1[node])
        return 0;
    if(v1[node] > 0)
        return v1[node];
    if(graf[node].size())
    {
        v1[node] = 0;
        v1[node] = dfs1(graf[node][0]);
        if(v1[node] > 0)
            v1[node]++;
        return v1[node];
    }
    return 0;
}

int dfs2(int node)
{
    if(!v2[node])
        return 0;
    if(v2[node] > 0)
        return v2[node];
    if(graf[node].size())
    {
        v2[node] = 0;
        v2[node] = dfs2(graf[node][0]);
        if(v2[node] > 0)
            v2[node]++;
        return v2[node];
    }
    return 0;
}

int dfs3(int nodeStart)
{
    int dist = 0, node;
    stack<int> s;
    s.push(nodeStart);
    v1[nodeStart] = 1;
    while(!s.empty())
    {
        node = s.top();
        s.pop();
        v1[node] = 1;
        if(!graf[node].size())
            return 0;
        if(graf[node][0] == nodeStart)
            return dist + 1;
        dist++;
        if(!v1[graf[node][0]])
            s.push(graf[node][0]);
    }
    return 0;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    p = P;
    n = N;
    m = M;
    graf.resize(2 * N + 1);
    auxgraf.resize(N + 1);
    for(int i = 0; i < 2 * N; i++)
        v2[i] = -1;
    for(int i = 0; i < M; i++)
    {
        if(auxgraf[R[i][0]].size() < 2)
            auxgraf[R[i][0]].push_back(R[i][1]);
        if(auxgraf[R[i][1]].size() < 2)
            auxgraf[R[i][1]].push_back(R[i][0]);
    }
    for(int i = 0; i < N; i++)
    {
        if(auxgraf[auxgraf[i][0]][0] == i && auxgraf[auxgraf[i][0]].size() > 1)
            graf[2 * i].push_back(2 * auxgraf[i][0] + 1);
        else
            graf[2 * i].push_back(2 * auxgraf[i][0]);
        if(auxgraf[i].size() == 2)
        {
            if(auxgraf[auxgraf[i][1]][0] == i && auxgraf[auxgraf[i][1]].size() > 1)
                graf[2 * i + 1].push_back(2 * auxgraf[i][1] + 1);
            else
                graf[2 * i + 1].push_back(2 * auxgraf[i][1]);
        }
    }
    //afis();

    cycle1 = dfs3(P * 2);
    for(int i = 0; i < 2 * N; i++)
        v1[i] = 0;

    cycle2 = dfs3(P * 2 + 1);
    for(int i = 0; i < 2 * N; i++)
        v1[i] = -1;

    //cout << cycle1 << ' ' << cycle2 << '\n';

    v1[P * 2] = 1;
    for(int i = 0; i < 2 * N; i++)
    {
        if(v1[i])
            v1[i] = dfs1(i);
    }
/*    for(int i = 0; i < 2 * N; i++)
    {
        if(i % 2)
            cout << i / 2 << "' " << v1[i] << '\n';
        else
            cout << i / 2 << " " << v1[i] << '\n';
    }
    cout << '\n';*/

    v2[P * 2 + 1] = 1;
    for(int i = 0; i < 2 * N; i++)
    {
        if(v2[i])
            v2[i] = dfs2(i);
    }
/*    for(int i = 0; i < 2 * N; i++)
    {
        if(i % 2)
            cout << i / 2 << "' " << v2[i] << '\n';
        else
            cout << i / 2 << " " << v2[i] << '\n';
    }*/

    for(int i = 0; i < Q; i++)
    {
        c = 0;
        for(int j = 0; j < 2 * N; j += 2)
        {
            if(v1[j] > 0 && !cycle1 && G[i] - v1[j] + 1 == 0)
                c++;
            else if(v2[j] > 0 && !cycle2 && G[i] - v2[j] + 1 == 0)
                c++;
            else if(G[i] - v2[j] + 1 >= 0 && v1[j] > 0 && cycle1 && (G[i] - v1[j] + 1) % cycle1 == 0)
                c++;
            else if(G[i] - v2[j] + 1 >= 0 && v2[j] > 0 && cycle2 && (G[i] - v2[j] + 1) % cycle2 == 0)
                c++;
        }
        answer(c);
    }
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4500 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4500 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 8 ms 8540 KB Output is correct
12 Correct 18 ms 11100 KB Output is correct
13 Correct 30 ms 24992 KB Output is correct
14 Correct 54 ms 26452 KB Output is correct
15 Correct 58 ms 26960 KB Output is correct
16 Correct 45 ms 20812 KB Output is correct
17 Correct 41 ms 18516 KB Output is correct
18 Correct 18 ms 11168 KB Output is correct
19 Correct 55 ms 26668 KB Output is correct
20 Correct 60 ms 26968 KB Output is correct
21 Correct 46 ms 20564 KB Output is correct
22 Correct 50 ms 18572 KB Output is correct
23 Correct 55 ms 28752 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4500 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 8 ms 8540 KB Output is correct
12 Correct 18 ms 11100 KB Output is correct
13 Correct 30 ms 24992 KB Output is correct
14 Correct 54 ms 26452 KB Output is correct
15 Correct 58 ms 26960 KB Output is correct
16 Correct 45 ms 20812 KB Output is correct
17 Correct 41 ms 18516 KB Output is correct
18 Correct 18 ms 11168 KB Output is correct
19 Correct 55 ms 26668 KB Output is correct
20 Correct 60 ms 26968 KB Output is correct
21 Correct 46 ms 20564 KB Output is correct
22 Correct 50 ms 18572 KB Output is correct
23 Correct 55 ms 28752 KB Output is correct
24 Correct 2 ms 4444 KB Output is correct
25 Correct 76 ms 8540 KB Output is correct
26 Correct 104 ms 11356 KB Output is correct
27 Correct 735 ms 25044 KB Output is correct
28 Correct 774 ms 26596 KB Output is correct
29 Correct 907 ms 26960 KB Output is correct
30 Correct 477 ms 20816 KB Output is correct
31 Correct 459 ms 18776 KB Output is correct
32 Correct 111 ms 11100 KB Output is correct
33 Correct 773 ms 26712 KB Output is correct
34 Correct 859 ms 26960 KB Output is correct
35 Correct 476 ms 20640 KB Output is correct
36 Correct 846 ms 18768 KB Output is correct
37 Correct 577 ms 28804 KB Output is correct
38 Correct 1392 ms 35668 KB Output is correct