oj.uz

Submission #299189

# Submission time Handle Problem Language Result Execution time Memory
299189 2020-09-14T14:37:00 Z ToMmyDong Tropical Garden (IOI11_garden) C++17
49 / 100
 189 ms 40812 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& printRng (ostream& os, IT bg, IT ed) {
    os << "{";
    for (IT it=bg; it!=ed; it++) {
        if (it == bg) os << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T>& v) {return printRng(os,ALL(v));}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {return os<<"("<<v.X<<","<<v.Y<<")";}
#else
#define debug(...)
#endif
#include "garden.h"
#include "gardenlib.h"

const int INF = 0x3f3f3f3f;
int n, m, p;
struct Edge {
    int to, w, id;
    bool operator < (const Edge &e) const {
        return w < e.w;
    }
};
vector<int> ed;
vector<vector<Edge>> edge;
vector<int> to, csz, dis, dfn, cdis;

const int MAXN = 150002*2;
const int MAXLG = __lg(MAXN) + 1;
int anc[MAXLG][MAXN];

int tme = 0;
int init;
void make_csz (int nd) {
    dfn[nd] = tme++;
    csz[nd] = INF;
    if (csz[to[nd]] == -1) make_csz(to[nd]);
    else if (csz[to[nd]] == INF) {
        if (dfn[to[nd]] >= init) {
            csz[to[nd]] = tme - dfn[to[nd]];
            int y = to[nd];
            for (int j=0; j<csz[to[nd]]; j++) {
                cdis[y] = 0;
                y = to[y];
            }
        }
    }
    csz[nd] = csz[to[nd]];
    if (cdis[nd] != 0) cdis[nd] = cdis[to[nd]] + 1;
}

void make_dis (int nd) {
    dis[nd] = INF;
    if (dis[to[nd]] == -1) make_dis(to[nd]);
    dis[nd] = dis[to[nd]] + 1;
}

void build () {
    for (int i=0; i<m*2; i++) {
        anc[0][i] = to[i];
    }

    for (int j=1; j<MAXLG; j++) {
        for (int i=0; i<m*2; i++) {
            anc[j][i] = anc[j-1][anc[j-1][i]];
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    edge.resize(N);
    n = N;
    m = N;
    p = P;

    srand(time(0));
#ifdef tmdd
    p = rand() % n;
    for (int i=0; i<Q; i++) {
        G[i] = rand() % 30 + 1;
    }
    debug(P);
#endif
    int cnt = 0;
    for (int i=0; i<M; i++) {
        int u = R[i][0], v = R[i][1];
        edge[u].pb({v, i, cnt++});
        edge[v].pb({u, i, cnt++});
    }
    ed.resize(cnt);
    for (int i=0; i<n; i++) {
        for (auto e : edge[i]) {
            ed[e.id] = e.to;
        }
    }
    to.resize(cnt), csz.resize(cnt, -1), dis.resize(cnt, -1);
    dfn.resize(cnt, 0);
    cdis.resize(cnt, -1);
    for (int i=0; i<n; i++) {
        sort(ALL(edge[i]));
    }

    vector<int> start;
    for (int i=0; i<n; i++) {
        for (const Edge &e : edge[i]) {
            int x = e.to;
            if (x == p) dis[e.id] = 0;
            if (SZ(edge[x]) == 1) {
                to[e.id] = edge[x][0].id;
            } else {
                to[e.id] = edge[x][edge[x][0].w == e.w ? 1 : 0].id;
            }
        }
        start.eb(edge[i][0].id);
    }
    build();
    debug(to);
    debug(start);
    debug(ed);

    for (int i=0; i<cnt; i++) {
        if (csz[i] == -1) {
            init = tme;
            make_csz(i);
        }
    }
    debug(cdis, csz);
    for (int i=0; i<cnt; i++) {
        if (dis[i] == -1) {
            make_dis(i);
        }
    }

    vector<int> res(Q);
    for (int i=0; i<n; i++) {
        vector<pii> qry;
        if (dis[edge[i][0].id] >= INF) continue;
        for (int j=0; j<Q; j++) {
            int id = edge[i][0].id;
            int d = G[j] - 1;
            if (d > cdis[id]) {
                d = cdis[id] + (d-cdis[id]) % csz[id];
            }
            qry.eb(d, j);
        }
        sort(ALL(qry));
        debug(i, qry);
        int cur = 0;
        int x = edge[i][0].id;
        for (auto &[stp,id] : qry) {
            int dl = stp - cur;
            for (;dl;dl-=-dl&dl) {
                int l = __lg(-dl&dl);
                x = anc[l][x];
            }
            if (ed[x] == p) {
                res[id]++;
                debug(x, p);
            } 
        }
    }

    for (int _=0; _<Q; _++) {
        answer(res[_]);

        /*
        int ans = 0;
        for (int x : start) {
            if (dis[x] < G[_]) {
                ans += (G[_] - 1 - dis[x]) % csz[x] == 0;
            }
        }
        */

        /*
        int ans = 0;
        for (int x : start) {
            for (int i=0; i<G[_]-1; i++) {
                x = to[x];
            }
            if (ed[x] == p) ans++;
        }
        if (ans != res[_]) {
            debug(G[_], ans, res[_]);
        }
        assert(ans == res[_]);
        */

        /*
        for (int i=0; i<N; i++) {
            int x = i;
            int prv = -1;
            for (int j=0; j<G[_]; j++) {
                debug(x);
                if (edge[x][0].w != prv || SZ(edge[x]) == 1) {
                    prv = edge[x][0].w;
                    x = edge[x][0].to;
                } else {
                    prv = edge[x][1].w;
                    x = edge[x][1].to;
                }
            }
            debug(i, x);
            ans += x == p;
        }
        */
    }
}


/*
6 5 2
1 3
0 1
1 2
3 4
3 5
5
32 4 2 1 23 
0 0 0 0 0
 */

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 672 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 5 ms 1408 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 672 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 5 ms 1408 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 17 ms 7040 KB Output is correct
12 Correct 41 ms 12924 KB Output is correct
13 Correct 66 ms 29168 KB Output is correct
14 Correct 156 ms 39964 KB Output is correct
15 Correct 189 ms 40812 KB Output is correct
16 Correct 155 ms 31472 KB Output is correct
17 Incorrect 154 ms 28788 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 672 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 5 ms 1408 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 17 ms 7040 KB Output is correct
12 Correct 41 ms 12924 KB Output is correct
13 Correct 66 ms 29168 KB Output is correct
14 Correct 156 ms 39964 KB Output is correct
15 Correct 189 ms 40812 KB Output is correct
16 Correct 155 ms 31472 KB Output is correct
17 Incorrect 154 ms 28788 KB Output isn't correct
18 Halted 0 ms 0 KB -