Submission #343550

#	Time	Username	Problem	Language	Result	Execution time	Memory
343550		Aldas25	Tropical Garden (IOI11_garden)	C++14	100 / 100	2890 ms	64976 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

const int MAXN = 300100, MAXK = 31;

int n, m, p;
vii adj[MAXN];
int par[2*MAXN][MAXK];

int getId (int v, int b) {
    return (b*n + v);
}

/*int lift (int v, ll x) {
    FOR(i, 0, MAXK-1)
        if (x & (1ll<<i))
            v = par[v][i];
    return v;
}

int getAns (ll k){
    int ret = 0;
    //k--;
    FOR(i, 0, n-1) {
        int lifted = lift(i,k);
          //  cout << " k = " << k << " i = " << i << " lifted = " << lifted << endl;
        if (lifted == getId(p, 0) || lifted == getId(p, 1)) {
            ret++;
        }
    }
    return ret;
}*/

bool vis[MAXN];
stack<int> cycle;

int toP[MAXN][2];
bool inCycle[MAXN][2];
int cycleLen[2];

void checkCycle (int v, int st, bool b) {
    vis[v] = true;
    int u = par[v][0];
    cycle.push(v);
    if (!vis[u])
        checkCycle(u, st, b);
    else {
        if (u == st) {
            inCycle[st][b] = true;
            cycleLen[b] = (int)cycle.size();
            int cur = 0;
            while (!cycle.empty()) {
                int x = cycle.top();
                inCycle[x][b] = true;
                cycle.pop();
                cur++;
                if (x != st) toP[x][b] = cur;
            }
        } else {
            while (!cycle.empty()) {
                cycle.pop();
            }
        }
    }
}



void dfs (int v, bool b) {
    if (inCycle[v][b]) return;
    toP[v][b] = -1;
    vis[v] = true;
    int u = par[v][0];
    if (!vis[u])
        dfs(u, b);

    if (toP[u][b] == -1) toP[v][b] = -1;
    else toP[v][b] = toP[u][b] + 1;

    if(v==getId(p,b)) toP[v][b] = 0;
}

int getAns (ll k) {
    int ret = 0;
    FOR(i, 0, n-1) {
        bool ok = false;

        FOR(b,0,1) {
           // cout << " i = " << i << " b = " << b << " toP = " << toP[i][b] << " incycle= " << inCycle[i][b] << endl;

            if (toP[i][b] == -1) continue;
            ll rem = k - toP[i][b];
            if (rem > 0 && cycleLen[b] > 0 && ((rem % cycleLen[b]) == 0))
                ok = true;
            else if (rem == 0) ok = true;
        }

        if (ok) ret++;
    }
    return ret;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    m = M;
    p = P;
    FOR(i, 0, m-1) {
        int u = R[i][0];
        int v = R[i][1];
        adj[u].pb({i, v});
        adj[v].pb({i, u});
    }

    FOR(v, 0, n-1) FOR(b, 0, 1) {
        int fr = getId(v, b);
        int u = (b < (int)adj[v].size() ? adj[v][b].s : adj[v][0].s);
        int b2 = (adj[u][0].s == v);
        int to = getId(u, b2);
        par[fr][0] = to;
       // cout << " fr = " << fr << " to = " << to << endl;
    }

    /*FOR(j, 1, MAXK-1) FOR(i, 0, getId(n-1, 1))
        par[i][j] = par[par[i][j-1]][j-1];*/

    int mxn = getId(n-1, 1);
    //cout << " a" << endl;
    FOR(b, 0, 1) {
        FOR(i, 0, mxn) vis[i] = false;
        checkCycle(getId(p, b), getId(p, b), b);
    }
    //cout << " b " << endl;
    FOR(b, 0, 1) {
        FOR(i, 0, mxn) vis[i] = false;
        FOR(i, 0, mxn) {
            if (!vis[i])
                dfs(i, b);
        }
    }
    //cout << " c" << endl;

    for(int i=0; i<Q; i++) {
        ll k = G[i];
        int ans = getAns (k);
        answer(ans);
    }
}

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