제출 #999365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999365		popu	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	1392 ms	35668 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31