Submission #343529

#	Time	Username	Problem	Language	Result	Execution time	Memory
343529		Aldas25	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5061 ms	48876 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 = 150100, 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;
}

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];

    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: 0 / 31