제출 #62419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62419		fallingstar	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	100 / 100	4050 ms	119812 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <map>

using namespace std;

typedef pair<int, int> pii;

const int N = 1.5e5 + 2;
const int INF = 1e9 + 1;

int n, m, src;
pii org[2];
vector<int> g[N];
stack<pii> st;
map<pii, int> vst, f[2], r[2];
vector<pair<pii, pii> > a;

void Dfs(int u, int p)
{
    pii pre(p, u);
    pii e(u, g[u].size() > 1 && g[u][0] == p ? g[u][1] : g[u][0]);
    f[0][pre] = f[1][pre] = -1;
    if (vst.find(e) == vst.end())
    {
        vst[e] = 1;
        st.push(e);
        Dfs(e.second, u);
        vst[e] = 2;
	    r[0][pre] = r[0][e];
	    r[1][pre] = r[1][e];

	    if (pre == org[0]) f[0][pre] = 0;
	    else if (f[0][e] != -1) f[0][pre] = f[0][e] + 1;

	    if (pre == org[1]) f[1][pre] = 0;
	    else if (f[1][e] != -1) f[1][pre] = f[1][e] + 1;
    }
    else if (vst[e] == 1)
    {
        for (int i = 0; ;++i)
        {
            auto top = st.top(); st.pop();
            if (top == org[0]) f[0][pre] = i;
            if (top == org[1]) f[1][pre] = i;
            ++r[0][pre];
            ++r[1][pre];
            if (top == e) break;
        }
        if (f[0][pre] == -1) r[0][pre] = -1;
        else f[0][pre] = (r[0][pre] - f[0][pre]) % r[0][pre];

        if (f[1][pre] == -1) r[1][pre] = -1;
        else f[1][pre] = (r[1][pre] - f[1][pre]) % r[1][pre];
    }
    else
    {
        r[0][pre] = r[0][e];
	    r[1][pre] = r[1][e];

	    if (pre == org[0]) f[0][pre] = 0;
	    else if (f[0][e] != -1) f[0][pre] = f[0][e] + 1;

	    if (pre == org[1]) f[1][pre] = 0;
	    else if (f[1][e] != -1) f[1][pre] = f[1][e] + 1;
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N, m = M, src = P;
    for (int i = 0; i < m; ++i)
    {
        int u, v; u = R[i][0], v = R[i][1];
        if (g[u].size() < 2) g[u].push_back(v);
        if (g[v].size() < 2) g[v].push_back(u);
    }

    org[0] = {src, g[src][0]};
    org[1] = {src, g[src].size() > 1 ? g[src][1] : -1};
    for (int u = 0; u < n; ++u)
    {
        while (!st.empty()) st.pop();
        pii e(u, g[u][0]);
        if (vst.find(e) == vst.end()) Dfs(u, -1);
        a.push_back({{f[0][e], r[0][e]}, {f[1][e], r[1][e]}});
        //cerr << f[0][e] << ' ' << r[0][e] << ' ' << f[1][e] << ' ' << r[1][e] << '\n';
    }
    int q = Q;
    for (int i = 0; i < q; ++i)
    {
        int x = G[i], ans = 0;
        for (auto p: a)
        {
            auto satis = [](int x, pii q) -> bool { return q.first != -1 && (x == q.first || (x > q.first && q.second != -1 && (x - q.first) % q.second == 0)); };
            ans += satis(x, p.first) || satis(x, p.second);
        }
        answer(ans);
    }
}

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