Submission #998885

#	Time	Username	Problem	Language	Result	Execution time	Memory
998885		popu	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	4444 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;

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 + 2;
        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]);
        }
    }

    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;

    v1[P * 2] = 1;
    for(int i = 0; i < 2 * N; i += 2)
    {
        if(v1[i])
            v1[i] = dfs1(i);
    }

    v2[P * 2 + 1] = 1;
    for(int i = 0; i < 2 * N; i += 2)
    {
        if(v2[i])
            v2[i] = dfs2(i);
    }

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

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31