Submission #255148

#	Time	Username	Problem	Language	Result	Execution time	Memory
255148		SamAnd	Tropical Garden (IOI11_garden)	C++17	100 / 100	3022 ms	42400 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pari
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 300005;

int n, f;
vector<int> sg[N];
vector<int> g[N];

int u[N];

int s;
int c[N];
bool dfs(int x)
{
    c[x] = 1;
    if (c[u[x]] == 1)
    {
        s = x;
        c[x] = 2;
        return true;
    }
    if (c[u[x]] == 0)
    {
        if (dfs(u[x]))
        {
            c[x] = 2;
            return true;
        }
    }
    c[x] = 2;
    return false;
}

vector<vector<int> > vv;
int ci[N], cj[N];
bool cc[N];
int d[N];

void dfs1(int x)
{
    if (c[x] == x)
        d[x] = 0;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (cc[h])
            continue;
        c[h] = c[x];
        d[h] = d[x] + 1;
        dfs1(h);
    }
}

int ans[N];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    f = P;
    for (int i = 0; i < M; ++i)
    {
        int x = R[i][0];
        int y = R[i][1];
        sg[x].push_back(y);
        sg[y].push_back(x);
    }

    for (int x = 0; x < n; ++x)
    {
        int h = sg[x][0];
        if (sg[h][0] == x)
        {
            u[x] = h + n;
        }
        else
        {
            u[x] = h;
        }
    }
    for (int x = n; x < n + n; ++x)
    {
        int h;
        if (sz(sg[x - n]) == 1)
        {
            h = sg[x - n][0];
        }
        else
        {
            h = sg[x - n][1];
        }
        if (sg[h][0] == x - n)
        {
            u[x] = h + n;
        }
        else
        {
            u[x] = h;
        }
    }

    for (int x = 0; x < n + n; ++x)
    {
        g[u[x]].push_back(x);
    }

    for (int x = 0; x < n + n; ++x)
    {
        if (c[x])
            continue;
        if (dfs(x))
        {
            vector<int> v;
            for (int x = s; ; x = u[x])
            {
                v.push_back(x);
                if (u[x] == s)
                    break;
            }
            vv.push_back(v);
        }
    }

    for (int i = 0; i < vv.size(); ++i)
    {
        for (int j = 0; j < vv[i].size(); ++j)
        {
            int x = vv[i][j];
            ci[x] = i;
            cj[x] = j;
            cc[x] = true;
        }
        for (int j = 0; j < vv[i].size(); ++j)
        {
            int x = vv[i][j];
            c[x] = x;
            dfs1(x);
        }
    }

    {
        for (int i = 0; i < Q; ++i)
        {
            int kk = G[i];
            for (int xx = 0; xx < n; ++xx)
            {
                int x = xx;
                int k = kk;
                if (d[x] > k)
                    continue;
                k -= d[x];
                x = c[x];
                x = vv[ci[x]][(cj[x] + k) % sz(vv[ci[x]])];
                if (x == f || x == f + n)
                    ++ans[i];
            }
        }
    }

    if (!cc[f])
    {
        c[f] = f;
        dfs1(f);
        for (int i = 0; i < Q; ++i)
        {
            int k = G[i];
            for (int x = 0; x < n; ++x)
            {
                if (c[x] == f && d[x] == k)
                    ++ans[i];
            }
        }
    }

    if (!cc[f + n])
    {
        c[f + n] = f + n;
        dfs1(f + n);
        for (int i = 0; i < Q; ++i)
        {
            int k = G[i];
            for (int x = 0; x < n; ++x)
            {
                if (c[x] == f + n && d[x] == k)
                    ++ans[i];
            }
        }
    }

    for (int i = 0; i < Q; ++i)
        answer(ans[i]);
}

Compilation message (stderr)

garden.cpp: In function 'void dfs1(int)':
garden.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vv.size(); ++i)
                     ~~^~~~~~~~~~~
garden.cpp:133:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vv[i].size(); ++j)
                         ~~^~~~~~~~~~~~~~
garden.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vv[i].size(); ++j)
                         ~~^~~~~~~~~~~~~~

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